Add a salt. It doesn't even have to be that large because of the unlikelihood. Alternately, adding IP address as a hashed parameter should distinguish them well.
Do I understand you right, that you should add something to the user-generated usernames? This seems like something that would be rejected by users to me.