Have you tried Xcode 4? I'm not its biggest fan, but, it is a step up from Xcode 3 when it comes to refactoring. It can rename a class everywhere in your project, for example.
Xcode 4's refactoring is still quite poor. Renaming something is akin to a "find and replace all" in my experience. If two unrelated classes have the same method name, Xcode will rename all instances of both classes if you rename one of the methods.