When one of my PC's boots I get a screen message saying:- Windows Genuine Advantage Notification has encountered a problem and needs to close. We are sorry for the inconvenience.
This is a genuine installation purchased from a reputable supplier. It's not saying it's not genuine but that there's a problem and asks me to send an error report. I have sent the error report many times now and never get any response back.
It sounds as if the Windows Genuine Advantage program didn't install correctly. The link provided by Stuartli has a link on the page to a little program called "Remove WGA". Use this to remove WGA from your computer then let Windows updates put it back on and hopefully it will install correctly this time. Windows Genuine Advantage appears in "Add and Remove Programs" but can't be removed from there.