I had the same problem with iMessage.
These days Apple IDs are mostly email addresses and sometimes you can sign in using your email address eg johnsmith@mac.com and password.
the log ins of Face Time and IMessage on iOS 5 seem to assume this is the format you'll be using, but if you happen to have an earlier Apple ID where you use your full name or another user name, eg johnny smith OR captain america or something - then that needs to go in the ID line, rather than the email address that it appears to be asking for.Then your password, and then these apps can see your original account. After another region page iMessage asks for the email address and that's when you enter john.smth@mac.com
It took me a while to work it out in iMessage and I kept getting the "Unable o verify" message but it's easy, as long as you can remmeber your original user name/apple ID.