Windows 7 Activation Error 0xC004C003 - Activation code is blocked

I bought a new copy of Windows 7 Ultimate 64 and installed it on my computer which had Vista Ultimate 32 on it.  My hard drive is divided into two partitions, 200gig system; 550gig data.  After Windows 7 Ultimate 64 installed it was working fine so I went to activate my copy and got the Microsoft Error 0xC004C003.  I went to Microsoft Support and got the following:  
Error code 0xC004C003
When you try to use a MAK to activate one or more computers, you may receive the following error message:
The activation server determined the specified product key is blocked.
This issue may occur if the MAK is blocked on the activation server.
To work around this issue, contact the PA Call Center to obtain a new MAK, and then install and activate the system.
I contacted the reseller that I bought the software from and he checked it and it showed that the key code is good.  He also did some research and found a couple of online forums that showed if doing a "format" with Windows 7 and Vista installed previousily on the system where information is held in the BIOS that makes this happen.

I then used GPart to create a new partition on my harddrive and installed XP Pro which formatted the old part of the hard drive and installed.  Then I allocated and installed Windows 7 Ultimate again on the new partition of the hard drive.

I need to know if anyone has experienced this or has a way to remove that data or a work-around.
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Try going to the Windows Activation page. Instead of selecting "Activate" select "Change my product key". Type in your product key. It should automatically activate at that point.
jimtechAuthor Commented:
I went to "Change my product key" and tried that way and got same error.
You need to call Microsoft. See this for the phone number
jimtechAuthor Commented:
I did call Microsoft 3 times and talked with several reps there and got enough information to know I was not talking with anyone that was going to help me.  The last call was to the MSDN department which I was told I had a copy of and that the seller would have to call Microsoft to resolve the issue.  Product returned and refund accepted after 2 other keys were given to me and they would not work either.  When calling Microsoft the reps there would only help me with the original product key that packaged with the DVDs.  Strange!?!  Since no help was obtained from the experts on the site, moderators please delete the question.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Windows 7

From novice to tech pro — start learning today.