The disc that you just purchased....is it a restore cd...or the install cd with gateways name stuck to it?

If it was the restore CD, then it is possible that there was a hidden partition on your HD that actually had the installation program on it...when you did the format you might have wiped the hidden partition and thus the EULA.

If it was a full installation Cd then you should be able to boot to the CD.
restart your computer with the CD in and watch the prompts very closely.

Boot to CD press any key press enter
There should be a prompt that files are being installed on your computer

If you need to install...drivers press F6 ignore this prompt as it doesn't concern your computer

The EULA license should appear here and request press F8 to agree to the EULA press F8

Set up will now search your hardware and the next prompt will be that setup has found these (this) partition with XP installed press R for repair option or press enter to continue setting up XP on the selected partition. press enter to continue setting up XP....do not press R

The next prompt will be to to delete the Selected partition and install xp on the deleted partition or repair the installed operating system on that partition.. You can choose either one...deleting the existing partition will cause the partition to be wiped and reformatted completely losing any data that you have...by choosing this repair option (refered to as the 2nd repair option) xp will install itself over the old version and save your personal files and settings (in most cases)....all drivers and updates will need to be reinstalled. Just do not hit any keys when the system reboots and asks for you to press any key to boot to CD again.

once past that point it should go pretty easy. If for some reason the system hangs here or after reboot then there is a hardware problem. Remove all extra hardware from the computer....ie. 1 stick of ram, 1 harddrive, 1 optics drive, no phone modem or flash memory slots or USB connections.
Set the BIOS to default settings...no overclocking or monitoring.

Reboot and start completly over.

Try it that way and see if you can't get it installed. I think you hit the wrong repair option and caused all your problems!