You're going to have to boot from your Windows XP CD to reformat. In order to boot from the CD you're going to have to change something in the BIOS.
Depending on the brand of computer you have, getting in to the BIOS could be one of several keys. It could be the F5, F8, F9 or Del keys.
It usually says, as someone above mentioned, "Press xxx key to enter menu" or "Press xxx key to enter setup."
You'll want to press that key and enter the BIOS.
Once you're into the BIOS you're going to want to find the "Boot Menu" to set your "Boot Order". When you find the "Boot Menu" you'll want to make the "Atapi CD-ROM" the first thing to boot up and the Hard Drive second.
Once you've changed that, insert the CD into the CD-ROM drive. Then "Exit and Save" the BIOS.
The computer will begin to boot and a black DOS screen will appear and say, "Press any key to boot from CD..."
Once it says this, press a key. Then follow the on screen instructions to install Windows XP.
It will eventually say something like, "Format the Partition using the NTFS file System," be sure to select the one that does not have the "(Quick)" after it. Selecting the option with "(Quick)" will not solve your problem most likely.
(here's a picture http://www.mysuperpc.com/build/windows_xp_install_6.jpg - choose the one that is highlighted in that picture).
It's going to take a while to format the Hard Drive, so go watch tv or do some deadlifts or something...
After that just follow the on screen instructions.