It sounds like you got ripped off. They gave you a legit (OEM) disk, but they also gave you a bad key. It's either that, or you're a victim of the KB971033 update for WAM.
Check to see if you have the update KB971033 installed.
Windows Update > List Installed Updates
If it is installed, you can attempt to uninstall it, but from what I hear, that fails most of the time. If it does work, you can avoid downloading the update again by finding it in the Windows Update download list, right clicking and clicking hide.
If you think you might have a bad cd key, you can call up Windows and ask them why the key is being blocked. They'll be able to tell you if your key has been flagged as pirated.