I wanted to add some information to some other answers here.
Archenoth's answer points out you can get more information from running Preview on the rename operation. It took me a while to figure out how to get to preview: type the rename keystroke a second time to get the dialog. Sometimes Preview didn't give the error information (and neither did the quick rename without the ppoup) but clicking OK in the dialog did say more.
MutantXenu found information in the logs by going into files in the workspace, but you can also get to these within Eclipse by going to the Error Log view (from Cmd-3)
When I had this problem, the error log pointed me to this failed assertion: "Search for method declaration did not find original element" which led to some unresolved bugs. (I'm running Kepler, but the problem is apparently hard to replicate and I don't see evidence it's resolved. See here and here.)
You can see if you're experiencing this specific bug by selecting the method and using Cmd-G (or Ctrl-G: Search > Declarations > Workspace). Eclipse is unable to find the method you're trying to rename and the search comes up empty.
My case suggests it's possible the error might have to do with identically-named methods in different classes. When the problem is occuring with one method, it doesn't affect most others.
Refresh, Project->Clean, and restarting Eclipse were not helpful to me.
Kevin's answer worked for me: "Try to delete the project from Eclipse (don't delete project contents on disk) and then reload it."