Well, the recovery disk should be bootable, and re-format it for you. I reommend letting the recovery disk do the formatting for you, and be careful, because cd-rom drivers are difficult to put on a boot disk...
Otherwise, do this:
1. Make a boot disk, you can go to a dos prompt and do
format a:
sys a:
2. copy the format.com (I think it's format.com) to the floppy disk. You can find it by doing start->find->files or folders and search for format on the c-drive.
3. Re-boot with the floppy disk in the drive, and the computer should boot to a dos prompt.
4. type a:\format c: to format the drive.
This should format it, but note that if you have a cd-rom drive, this disk will not load the cd-rom drivers. You will need to be able to load them to re-install your data, unless the CD-ROM drive is bootable.