The Product Key can be changed by performing a "repair install" using your new genuine Windows XP Product Key and the Windows XP CD that came with it.
Try the following first:
The Genuine Advantage Product Key Update Tool is only valid for users attempting to change their current non-genuine Product Key to a genuine COA sticker or genuine Product Key - all without a reinstall! http://go.microsoft.com/fwlink/LinkId=50346&clcid=0x409
If this utility does not work in your situation, you can try a "Repair Install". And if that does not work, your last option is to perform a "Clean Install".
How to Perform a Repair Install of Windows XP: http://www.michaelstevenstech.com/XPrepairinstall.htm
Clean Install Windows XP: http://www.michaelstevenstech.com/cleanxpinstall.html