Same sort of problem here.
Have been using Nickname X on Gamecenter for months,
Upgraded to iOS 5 today.
Gamecenter said I had to accept new terms and conditions.
Used E-mail associated with my Apple ID to log into Gamecenter and it asked me to enter my nickname.
Typed the WRONG nickname accidentally. Call it Nickname Y.
Now I can no longer associate Nickname X with Gamecenter. If I log out of gamecenter and log back in, it always says "Welcome back, Y". All my save games and achievements are associated with nickname X, so I get nagged during every game that I am logged in as the wrong person.
Other people are saying that when they were prompted for the nickname, they entered their correct nickname, but Gamecenter said it was taken and would not allow it. So I'm assuming that the fact I entered the wrong nickname was not the issue.
If I edit the account in Gamecenter app and try to change my nickname to nickname X, it complains that nickname X is associated with a DIFFERENT account. How can that be? I mean, both nicknames are associated with the exact same Apple ID and password.
This is highly frustrating.