If you bought this system new, then you should be able to simply call the activation phone number, explain the situation, and get everything resolved.
If you got this system used, or it didn't come with XP from the factory, you're going to have a tougher time of it. So I hope you saved the COA (Certificate of Authenticity) paper that comes with any legal copy of XP. Without it, you're probably never going to have any luck convincing Microsoft your copy is legal.
Officially, Microsoft claims that only some small fraction of people are being hit by the false-positive problem with "genuine" advantage. Unofficially, the problem is almost certainly much wider spread, probably affecting up to 10% or more of all Windows users.
A lot of people seem to be getting bit by this as a result of work having been done on their systems by third parties as well. Smaller shops will sometimes load pirated copies onto people's systems to make a few extra bucks. Unfortunately, even if you could prove that's what happened to you, you're still going to get shafted by having to buy a new license.
Unfortunately, the only party that really has a genuine advantage from the genuine advantage program is Microsoft. It's a program slanted in their favor, marketed as some consumer protection mechanism. While it does help out some of the smaller computer shops that are actually honest and only install legal software, everyone else gets a good shafting in a place that rarely sees the light of day.
I have a "Shadow Star Icon" from a Microsoft website informing me that Microsoft is unable to validate my operating system. It launches everytime I start the computer and several times throughout the day. At startup the computer will not get to the home screen without making a selection of whether to correct now or later. It offers me the opportunity to "purchase validation." Everything on my computer is legitemate.
I've looked in the System Configuration Utility (msconfig.exe) startup and services and don't recognize it.
I have a HP Pavilion a647c, w/Windows XP. This is the site that it directs me too:
If you scroll to the 3rd section of the webpage you will see the "star" that I refrenced earlier.
Bottom line is I don't know if this is for real. Please help.