Have patients . . . we can fix this!
Attempt to Activate over the Internet. When that fails, one of the options is to change the Product Key . . . follow this (using the new key from the product you just purchased), and try again.
If this is not successful, then try the telephone method. It will take you through an automated re-activation process. If it still fails, then you will be told to stand by to talk to a real person.
This is the part where PATIENTS comes into play! You will be talking to some underpaid and overworked support person over in India where Microsoft has outsourced this function. They can be a bit hard to understand, so listen carefully, be polite, and HAVE PATIENTS. If you insult this person excessively, they WILL hang up on you and then you have to start all over again.
If this person reaches the point where they say they cannot help you, then very nicely thank him for all his trouble and ask to be connected to someone who would have the authority to manually complete the Activation. You will be placed on hold for a few minutes and eventually get someone (who usually speaks better English) and you will have to explain it all over again and they will go over all the questions asked by the previous person (many of which will seem rather stupid given the explaination you have already given), and eventually they will get you back to the window where you will enter the Product Key they give you.
Now, all of this pre-supposes that you have: #1 - Successfully completed the Repair Reinstall I outlined in my original note, and #2 - You have actually purchased a legitimate copy and you have the Key from the CD case (retain version) or the Product Key Sticker (OEM version).
I usually get my problem resolved in either the automated re-activation process, or the first live person I talk to after that. I have only had to go the supervisor to finally get it fixed one time, and I have been in the computer service business for over 20 years, so I know this will work!