Genuine product key not accepted for validation

I bought a genuine copy of Windows 7 64 bit, I know this for sure, 100%. It was bought from Amazon (actual amazon, not a 3rd party using amazon) and has all the correct holography.

I have been using it for a while on a different pc, however, after some hardware issues, replaced various bits of hardware and after MANY reinstalls later, I manage to get windows working properly, I finally have a pc that doesn't have any hardware faults, although now windows tells me:

The product key you entered can't be used to activate windows.

What is the meaning of this? I bought a genuine copy of windows so that this doesn't happen.

Can someone please assist.

Probably a phone call to Microsoft to get it activated will get it sorted out for you. It's likely just the fact that it was recently put on a machine and now being moved. MS systems would see this as you installed it and gave it to a friend a week later.