The problem with changing usernames is that it's a caching issue and that it breaks /author/username URLs.
The URL breaking issue is obvious.
The caching issue is less obvious. If you're using a persistent object cache like memcached or something, then the username will be stored in that cache, and thus it won't change properly until the cache runs out.
On a simple site setup, this doesn't happen because it doesn't have persistent object caching. On a complex one, it becomes a real problem. A fair number of changes to the user system would be needed to allow the caching to be taken care of properly.
A core feature request was rejected for this because of the limited need for it, basically. However, a core patch to correct the caching issue might be better considered, allowing for a much simpler plugin to change the username (or a simple patch to allow same, once the caching issue is cleared up).