Well, I might as well thow my name into the hat with this exact same problem. Got the game from Gamestop here in Newark Ohio, and I go to register, and gives me the invalid serial number. I was shocked, so I tried multiple times changing zeros to O's and yeah, same thing. I sent an email to the support, but I did not check here first to add the pictures of the box and serial key sticker.
I think what's going on here, is that somewhere through the chain before it's getting to the retail store, that someone is repacking the game, or that multiple serial keys that are exactly the same are being distributed by accident to multiple games. What I mean is, there could be many games with the exact same serial key. I could understand this problem, because I've had games back in the day that had the same serial key as another person.
I'd have to stress to everyone that seems right p-o'd that you need to show some restraint and patience, because we are not the only ones facing this problem. Their system is distributing serial keys that are exactly the same to multiple people without even realizing it's doing it, or it's a person doing it. You can't blame the retailer's (best buy, eb, gamestop) because they have zero control over how the serial keys get distributed, and do not put serial keys on any games. The only place I believe does that, is where the game is being packaged. So, if they use an automated system to generate serial keys, they really need to check that for a bug, or a printing error.
Anyway, just send an email, like we've all done, so that you get into the support queue, then just follow whatever they ask of you so that you get it resolved. If you already are getting support and there isn't a result for you yet, continue to be patient because they are having to deal with (potentially) millions of people that have this exact same problem. So, chill out, and try and play another game to take yer mind off this. That's all I can really say about it. I have the same problem, and I'm just a joe shmoe.