Quick dirty explanation of how Windows Genuine Notification works: it checks a certain set of files in the system. So long as those files are unaltered in any way, and the serial checks out, it'll consider your Windows genuine and inform Microsoft of your device IDs (the primary components of the system, such as motherboard chipset, CPU, GPU, etc).
Three things can cause the genuine notification to fail: firstly, if there is a clash in device IDs known to Microsoft (i.e. if they think the serial has been used on multiple computers). This can be because of a change in hardware (e.g. the motherboard), or because it's been installed on another computer. Call MS to fix it - it'll take a couple minutes. Secondly, if any of the files it checks has been altered (like the WAP removal patch or the time-stop patch), it'll automatically flag your copy of Windows as non-genuine. This is typically fixed with a fresh install from a retail disc, and CAN OCCUR AS A RESULT OF A VIRUS/ANTI-VIRUS. You can try calling Microsoft incase it's just a case of Windows "forgetting" that it's activated (sometimes happens when you move house), but they will be able to tell if those files have been altered and often tell you to reinstall Windows.
Finally, the serial number itself could be a fake/counterfeit/re-used/re-sold serial, and you could really be the victim of counterfeit software. In that case, you're SOL. You can try calling Microsoft to check, but you're probably gonna have to buy another serial/license key.
