To be Genuine, means that the license has to be original and authentic. The copy installed is either pirated, the serial has been used more than max times allowed, its and OEM version that had problems activating, or you installed windows and when it asked you for a serial you typed your OEM serial.
If you own a legit (legal) copy of the seial whether virtual or printed from software you purchased from Microsoft or a Re-seller then contact Microsoft and they will try to fix it.
If it is an OEM copy (Copy that came preinstalled on your laptop or copy that you installed from a manufacturer disc [the windows anytime upgrade is NOT a manufacturer disc]) then contact your manufactuer (dell, gateway, hp, fugitsu, acer, etc.)
If it is a serial that you obtained free (aka stealing, keygen, torrent, warez, or pirated) then it is problably illegal and not legit meaning you either have to buy a copy of Vista or get linux or be uneligible to recive updates from MSFT Update
*Note: If you are caught with an OS that is not legit (in other words and illegal operating system) you can be prosequted by law and be sent to jail or you might have to pay Microsoft a damage fee [which is more expensive that the OS you own illegaly] (if this applies to your OS)
To figure out if your copy is legit contact Microsoft if they tell you it is not legit then you can buy a copy through them or they can tell you to change OS (They won't ask you for personal information [or shouldn't] unless you are going to make a business transaction (i.e. buy a copy from them, get a serial exchange, diagnose your PC)