It's usually less of a hassle to install windows first, as it is often anal about other Operation Systems being installed on a hard drive. My thoughts would be to format all the partitions and install windows first. If you can't use the fdisk utilitie from a Win bootdisk, you could always use a bootable Linux cd. As far as I know it is possible to get into a console to access fdisk from the RedHat cds, but I can't remember how offhand. Someone on here should know though, or you could try and look on google. (You can boot into a console on the slackware cd, which is what I use... not sure which other distros have it off hand)
Welcome to GLO!