Some follow up on this. Apparently I was wrong when I said that the username only appeared in the users table. After taking Mike's advice and greping through the database dump I found it other places. When I went back to phpMyAdmin and searched the live database *correctly* I also found it there :-)
It appears, for example in the comments table (if that users has ever commented on a post). And potentially other places.
So maybe I'm just confused somehow. Mike: when you did this, did you have issues with comments? Or else maybe this isn't a good way to go about changing a username.
I've also done a bit of searching on this, and found a number of places (wp stackexchange for example) where a number of people say a simple change of user_login in the users table *does* do the trick. There are also some plugins which claim to change a name. Wonder exactly what they do?
I also wonder how foolproof it actually is to delete a user and reassign their content to a new users. I wonder if that really gets everything?
In terms of plugins making use of the user_login (rather than the ID), it definitely appears that BuddyPress uses the user_login string rather than the ID for some things. And maybe bbPress. Again, unless I'm somehow very confused, which is certainly possible.