Return to Revisions

I've done this a few months ago (for different reasons). The steps I took (the language was Perl):

1. Rename the method. Alias the old name to the new name (this should not break any code, as the method can be called by either name).
2. Inform the rest of the developers about the name change and why, telling them to use the new name from now on.
3. Grep the code base for the old name, fix any occurrences.
4. Log any uses of the old name (using the old name should still work at this time). Fix those cases.
5. Wait (while doing 4.), until no more entries appear in the log.
6. Break the alias. Make a method using the old name that throws a fatal exception with a message about the name change.
7. After some time, remove the method with the old name.

Of course, your mileage will vary.