I think I have an idea for how to fix this (although I'm no expert on the matter). Do you dynamically generate the the user page every time it is accessed or is it saved as a static page after each time the user updates something? Would people update their pages more often or would people access them more often anyway?
If it's saved as a static page you could let the user create as many names with associated pages as they want without have to store them in a database. The only thing you would need stored is their username and id which are already there. The way I think it would work is in a comment or something in the static html page (or a seperate .txt with only the variables if each user has a folder with several pages) that the referer page check to see if it matches the current username associated with the id. If it does then it doesn't do anything, if it doesn't it deletes everything and replaces it with a header(Location: /path/correctUsername.html). Now if nobody takes the name it simply redirects to the correct one. If somebody takes the same name it will overwrite the redirect and old links will point to the new user, but there will be no broken links. I understand that this requires a certain amount of overhead, but as far as database intensity it's really just a single database query each time somebody accesses a username.newgrounds.com page which is minimal compared to the number of queries for the forum.
If they are dynamically generated each time then I'm pretty stumped. After writing this post and giving it some thought I'm pretty sure they must be or the pros would have figured this out. Oh well, it's all typed I'll post it anyway.