Vista product key registration bullshit

Hey, I just bought a brand new computer today with vista already installed in it from HP. When I set it up though, after I set my account on it, it told me my product key was invalid and I couldn't even get onto the desktop. So I called CompUSA where I bought it, tech guy tells me to ask Microsoft for a new product key, Microsoft shuffles me to HP who tell me to check back with CompUSA. Ugh, so I talk to the manager at CompUSA and get them to take a look at it but now I won't get it back until mid-day tomorrow. Everyone I talked to said they never heard this before. Anyone here know anything about it?