For what it's worth, I have the exact same problem. Bought at BestBuy, invalid CD key, sent email to support... no response yet, but I will try to come back and edit once I hear from them.
I don't know if this has anything to do with anything, but the sticker containing the serial key is labeled: TAKE TWO INTERACTIVE... isn't Stardock the publisher of this game, and Gas Powered the developer? Where does Take Two come into this?
I also wanted to say: I made sure not to buy this game from Gamestop... breaking street date the way they did is unforgiveable, and I completely feel for the developers of this game and the headache they undoubtedly had to endure over Easter weekend because of it.