Right now, RenameUser relies on lobbing jobs into the job queue. However, the job queue is not designed to handle tasks in a reliable, ordered manner.
RenameUser is complicated because of the way we typically pull the user name from the database. There are several places where we pull denormalized values for the user_text field in several tables (revision, archive, etc). If we actually go to the source (user_name field in the user table), then renaming would be a much cheaper and more robust operation.
Examples of this cleanup are r100286 and r100300. Aaron has done some of this work, but would like help.