UPDATE: As of Xcode 3.2 you can rename projects from the Projects->Rename dropdown.
UPDATE: Be sure to see my post about the shell script I wrote to rename from the command line.
For those wanting to rename their XCode project, here how you do it manually:
1) copy your project to a new folder, rename the folder to your new project name, delete the build directory in the new folder.
2) drag the entire new project folder onto the TextMate text editor
3) In TextMate, remove (delete references) to anything non-text such as images and sounds. [UPDATE: TextMate will ignore the non-text files, so step 3 is unnecessary.]
4) Replace in Project (old project name) with (new project name), save all files. Close TextMate.
5) Now drag the (project name).xcodeproj file into Text Mate, repeat Replace in Project processm, save all files. Close Text Mate. If you have spaces in your project name, look for all instances of your project with spaces replaced with underscores too.
6) Rename all files containing (old project name) to (new project name). Be sure to check the Classes directory too. If your project name contains spaces, look for all instances of filenames with spaces replaced with underscores too.
That's it! Your new project should be good to go. I don't think cleaning of targets is necessary, since the build directory is removed (correct me if I'm wrong though!)