What you need to do:
1. Get a bootable partitioner tool, like Parted Magic (check
here)
2. Boot the tool form the CD or floppy, and set the windows partition
active, if it's hidden.
3. Put in Windows installer CD, reboot computer.
4. Boot the Win installer CD, and install linux to the desired partition (the one you activated)
5. Windows
will overwrite your MBR, so Linux will not be available temporarily.
6. Boot your fedora CD and
a) search for options like "reinstall GRUB", or
b) "boot fedora from hard drive"
7. Reinstall GRUB into your MBR
Using GAG is a good solution too (I use it too), but you will still need to put a GRUB into the boot sector of your Linux partition to be able to boot Linux. And because of this I don't recommend using 2 bootloaders, when 1 is sufficient.
Good luck!