The software does not become not genuine because the computer was sold. Usually this message occurs because somebody or some company violated the license terms (installed it on more computers than was allowed), though not necessarily on the computer you have. For instance, a company might have gotten a bulk license, allowing them to install 10 copies. The company actually installed 9 copies. Then an employee installed another copy, possibly on a personal computer; or posted the license code on the Internet. Now the company installs a 10th copy. More copies have been installed than were purchased. Microsoft's authentication servers don't have any way of distinguishing between the authentic, authorized copies and the pirated copies, so the code is disabled for ALL copies.
Sometimes there are problems with Microsoft's authentication servers, and perfectly valid copies are flagged as invalid.
If the computer came with Windows XP installed, or a legal (single) upgrade was installed, there should be a sticker on the computer with a key number on it. See if you can enter that number. Or the key could be on the packaging for the upgrade. You should ask the person you got it from for the installation disk.
Microsoft is the only place that you can go to turn your copy into a "genuine" (authorized, as opposed to being installed from a CD from Microsoft) copy. You could call them to try to find out why it is flagged as not "genuine". You might have no recourse except to pay them, if they are even still doing that for XP (they discontinued it a few years back). There is a slight possibility that the computer manufacturer could help if this is the copy of Windows that was installed at the factory.
If you have a disk from Microsoft or the manufacturer, then you have a better chance of getting the issue resolved without extra cost. No guarantees though.
If you get a key from any other source, it is illegal and bogus; it might or might not work for a while, and might eventually be flagged as illegal, putting you back at square one.