Yeah, windows = crap for big hardware changes. Now, guys, he doesn't need to reformat, that'll lose all his data. All he has to do is reinstall a fresh copy of windows over his existing one.
Now, by how it's looking for a boot record only on the floppy, either you got a bad floppy disk in there, or you havn't setup your boot selection. Your bios probably hasn't fully adapted to your current setug I guess. Go into your bios, and look at the boot list. I suggest putting it floppy, cdrom, then IDE0/Hard drive name.. whatever your bios wants to call it.
So yes, fix up your boot list, then try reinstalling windows xp from the cd. You don't need a boot disk to do that. Windows xp cd comes with its own little boot record... so yep.
Btw, Fedora rocks. Changed a mobo n' cpu onnit, it detected it n' reconfigured itself automatically, oh, windows got pwned by a free open source OS.