Basically id have recently purged it's CD-KEY server. They do this from time to time. Unfortunately, the honest ones get cought up in their security server. For those that bought the game and still have this problem, you may need to call id to get a new KEY.
I only wish id would figure out a better way to validate it's customers.