Microsoft Genuine Advantage error when installing Service Pack 1

I recently upgraded my server. I have a genuine version of Windows Server
2003 w/o SP1. When I try to update via microsoft update or Windows Update I
get a Microsoft Genuine Advantage screen and procced to validate, then I get
an error saying unable to preform validation. It says I have encountered an
unknown error. Please contact local support for assistance.

When I try to install SP1, I get an error that Windows Server 2003 Service
Pack 1 cannot install. The product key used to install Microsoft Windows may
not be vaild. For more info go to www.howtotell.com.

I do not think that my key has been stolen, because on the old server, I
could update just fine. I did take the old server out of service, it is no
longer online and in fact i reformatted the hard drive for use in the new
server.

My question is, what do i need to do to resolve this? I really hope the
solution is not going out and buying another copy of server.

Thanks in advance,
Chris Brucker