Running a quick torrent search, there is a keygen for this game already. Mine was purchased through steam as well (yes, mine is legit). I did the "right" thing and waited for the game to be released and purchased it.
My key, for the moment, is working just fine.
However, having said that... The fact that there IS already a keygen for this game does not bode well. I suspect that the key algorithm will need to be updated and everyone given new keys before this is all said and done.
It seems that the "leaked" version of the game might not have had executable encryption enabled, nor debug threads disabled, thus allowing anyone with a little knowledge of how assembly works to simply observe the key algorithm at work and generate a working keygen.
*THIS* is why PC games cost just as much as console games. Because they have to go through a LOT more hurdles on an unsecured platform. This is the price we pay for our flexibility and freedom from proprietary hardware, software and licenses.
While I do feel for those of you whose keys don't work, I'd suggest you contact Steam and report the issue, as ultimately, THEY are the ones liable for the sale, not the publishers. The retailers are the ones that have to deal with bad sales.
And no, I'm not saying don't complain here. That'd be stupid... as you should be heard (I know I would be raising a stink if it were me). Just keep it polite, ya know? Karma has a way of sticking it to you if you're too over the top.
Cheers.