If you put the windoze cd in, boot from it, you'll eventually get to the fdisk menu and you can see what partitions are on the hard disk, what's available, what's unallocated for, etc. I don't see why you couldn't delete the Fedora partition from there, create a new one for windoze, format, and install windoze.
OR:
Maybe you could boot from the Fedora livecd, run gparted, and delete the actual hard disk install of Fedora (remember you'd be running from the livecd here). Apply changes, put windoze cd in, and go to town.
I don't see why neither of these would work. Try it and see what happens. But, by the way, gparted is included in livecds... isn't it?