If your previous key is invalid (I guess there is a registration key check as an undocumented part of the SP3 update, sneaky), then the only thing is to contact MS and see how you can get a valid key.
Assuming you have a legit copy and just the key is found as invalid, it isn't long ago that windows update flagged a number of legit keys as invalid, caused a bit of a stink in the media. Again the only way to resolve it is to contact MS.