I've used Avast for many years with XP, and I just don't think that it has anything to do with your system not being genuine.
It's a possibility, and happens regularly, repair shop copies of Windows comes back as non-genuine. Some of them gets their copies from questionable sources, for the lowest price possible. They may slide volume license copies to their customers, or copies obtained from TechNet or MSDN that are reserved for their customers. At some point, these copies will come back as non-genuine, although they run fine at first.
I'd highly suggest that you carry the computer back to the seller, explain the situation, and demand to "make things right", either by refunding your money in full, or giving you a new, genuine copy of Windows. In a shrink wrap package, a full retail (or OEM) package, unopened.
If by chance the seller doesn't cooperate, report them to Microsoft, they have a program that may help you get a new, legit copy of Windows at a greatly reduced price. But you'll have to cooperate with MS, and furnish any information that's asked about the purchase, including the seller's info.
Best of Luck,
Cat