I'm not sure this is a Fedora issue, as you are able to boot to the Windows cd without problem. Once you booted off it, that's Micrososft's code running.
You could boot off a DOS floppy or boot cd and remove all your partitions, effectively removing Fedora before installing Windows. However, I am not sure that would solve your problem.
You can get a DOS floppy image from here.
How do you know that the cd is a good one?