The computer case, not the CD case.
I would go call up Microsoft. I have had XP tell me the key I had could not be used on two different occasions. I had no trouble with MS either time. The process is a bit long, and you have to be able to handle a big giant number over the phone, but you can get new activation codes and even new CD keys this way.
One time during a phone call reactivation it was clear that the person I spoke to didn't have a clue about computers. I could have told her that the Gonculator Valve went bad and had to be replaced, which caused XP to need reactivation.
You don't have anything to lose, as far as I can see, by calling Microsoft. At worst, you will be no worse off than you are right now.