Yeah, a consent system would be good. I think that, if you did change your username, there would be a little label saying "my last username was 'xxxxx'" This way people could say, Oh, I know this person.
Maybe there could be a list on the signup page with cool, unused names, for people who can't think of any. Of course, it would have to be updated whenever someone made an account with that name, so no one tried to use a name twice.
