I never had any problems with Fedora Core 5 (Installed on 3 different computers), are you sure you had some non-partitioned space available when installing it?

If I remember correctly, you can use a DOS floppy and just type fdisk /mbr and it will work. (Even for XP) But I don't remember if it works or not.

You don't need a Linux or Windows CD to go in the BIOS. It's the screen before the computer boots.

If nothing works, use a DOS disk, go in fdisk and delete all the partitions, it's in the "Guides and Solved Issues" section
http://www.techspot.com/vb/menu31.html

Then, install Windows XP, but you'll have to leave less than your whole disk space for Windows. (Say, 40GB) Format it as FAT32. If you need instructions, ask. After, install FC5, but watch what it's doing with your HDD before installing in the partition step of the installation.

Make sure the copy of the Windows XP CD is bootable.

If you made your own copy of the origional XP CD and have not "cloned" it from the origional XP CD it wont boot into the CD.

Check this thread out: Windows XP CD doesnt boot.