Heh. Thats a classic. Hurra for restore cds.

Did you wipe the partition on which you install Xp?
Before ever running the setup program.
With recovercds, its an OEM key and that wont work if it sees
anything windows like during the install.

You cannot use this key if you install XP over the old install.
Its not considered a OEM install and hence you need different key.

I had the same problem and used XpKeyChanger to create a key that would allow me to
install over the old install allowing me to keep my settings.

This, however, its not legal and you might have problems using Windows Update.

Btw: Funny place to post about XP keys....