I dual boot OpenBSD (a *nix variant) with windows 2000. As the above poster said, you'll have to repartition your hard drive. Also depending on the bios you have, you might have to have your linux partition or a linux partition in the first 8GB of your hard drive. As for the actual dual booting, I use NTLDR, the windows 2000 boot loader and it works real easy. Probably the most important part is to make sure windows is installed first which you have done. Otherwise the windows installation will overwrite the masterbootrecord and make your linux system unbootable. A lot of people dual boot so if you google such things or check typical linux sites you'll find all the information you could want. Here's a good one:
http://linuxcourse.rutgers.edu/dualboot.php
It even mentions redhat specifically.
You should be using debian. ;-)