It's not that uncommon, so check the steps below for fixes..
First, follow the instructions in the link below for such an error:
http://support.microsoft.com/kb/2008385
There are a couple of Youtube videos regarding the issue as well. See below:
Try the following:
http://www.youtube.com/watch?v=DJAShAA9EDQ
If not, try this:
http://www.youtube.com/watch?v=75hk_ByK3HQ
________________________________
Next, if you can actually boot the computer,for issues regarding malware, follow the instructions in the link below to scan and remove any malware, spyware and adware.
http://forums.cnet.com/7726-6122_102-5509131.html?tag=posts;msg5518840
Next, remember that if you had a computer shop install your operating system, it's entirely possible they didn't install a fully legal version, even though they said they did. In such cases, through the passing of time and Microsoft's updates to their methods for checking authenticity, truth finally catches up to your version legality. Contact the repair shop if that's the case and ask for a legal version.
In a few cases, simply checking the activation status at Start-Computer- (RIGHT click on Computer, choose "Properties"), then look to the Activation Status area at the bottom of the screen, then closing the window and restarting the machine will fix the issue. If it's not activated, do so using the legal certificate of authenticity number online, or by callingl Microsoft.
Of course, if you're in a hurry, you're sure you've got a legal version of the OS, and you've got all your backups, then you're best bet is to wipe the hard drive, unplug all external USB hard drives from the computer, and reinstall everything back to its factory state using recovery discs, partitions, and backups. Sometimes its simpler and quicker to start over from scratch.
Unfortunately, there are a number of different things that can cause the "Windows not genuine" issue and the quickest and most effective remedy is to restore everything back to it's original condition.
Hope this helps.
Grif