Activating Windows Home Premium

Hi all,
Two years ago I bought a laptop with Vista Basic. I bought the Home
Premium upgrade from MS. They sent me an anytime upgrade DVD. The
product key was stored in MS digital locker. So I didn't record it
because MS was keeping it for me in my digital locker.
Last month the hard drive died. I replaced it. I installed the Vista
Basic and activated it from the sticker on the laptop. I then tried to
install Home Premium from the original anytime upgrade DVD. When I
went to the link from the receipt email the MS had sent me 2 years
ago, I find no way to get to this digital locker. I call MS and they
tell me that digital locker went away. So they generated a new Home
Premium product key.
I couldn't try that key at the time. When I was able to finally try
it, the key kept coming back as invalid. I call MS and this was a
disaster. I kept getting passed back and forth between activation and
customer support for almost 2 hours. I then get an activation person
who wants me to pay $59 for tech support. I had to explain to her that
I was not having a tech support problem, I was having an activation
problem. I then had a terrible customer service rep accuse me of
trying to scam free copies of the O/S. He said that the key that I
have is not valid (I read it to him and every ******* person I talked
to on the phone) He eventually offered to generate a new key for a
fee. Thanks but no thanks. I already paid for this, I am not paying
again.

The next day I called back and got a nice customer service rep. He
looks up my key and said that it was a valid OEM full install key for
that DVD that I had. As soon as he said this I thought ok, I was
trying to upgrade from Basic, and not doing a full install. So I'll
wipe the laptop and try again.

Tried a full install and the key comes back as invalid. @%*&^$#*&^.
Does anyone have any thoughts? A coworker mentioned that he remembered
MS having some issues with their activation keys and that they changed
algorithms. I don't have all the updates yet on this laptop (ie SP's)
He suggested I put all the SP's on and then try to activate.

Any help would be appreciated as calling MS has bee awful.

Thanks,
Dino