Maybe it's rare, and I was getting frustrated seeing other people resolve their situation by remembering that they had used a different Apple ID when I know I've only ever used one Apple ID (the e-mail address) but with no ability to reverse search from your nickname to your Apple ID there is no way to know for sure that you don't have a typo in the Apple ID your nickname is tied to. iOS 5 screwed all this up for me because it was the first time I was forced to relog into gamecenter, before that the phone just had my mistyped Apple ID stored and I never had a reason to retype it. Your Apple ID, even if it's an e-mail address, can be different than the e-mail that Apple uses to verify and communicate with you, so it's very possible, like in my situation, that you would never know there's a problem with your Apple ID until your forced to relog into gamecenter. So now, I have two Apple IDs, my real one with .com at the end that I use for updating apps, etc., and my gamecenter one with .con that I had no idea existed until I tested it this morning. My point is, until you had to relog into gamecenter with an Apple ID (and in my case as I would guess a lot of cases, this wasn't until I updated to OS5) there was no way to know if you had a typo in that gamecenter-associated Apple ID, and without Apple allowing us to find an Apple ID from a gamecenter nickname, there's no way to be sure.
And yea, thankfully Tiny Tower backs up localy, although I was getting really tired of the reminders that I wasn't logged in as my nickname.