When you install RH, do you enable LBA32 on the bootloader (lilo/grub)? If not:
When you installed W2k, was the harddisk already completely blank (i.e. had never had even the slightest resemblance of an OS on it, no partitioning or anything - straight from the shop)? I read somewhere that where most OSes, including the Win9x series, will use fixed partitions tables (so you have hda1/2/3/4 for your primary partitions, and hda5+ for you logical ones), the NT family will preferentially use dynamic partitioning (whatever that is), which might cause problems. If this is the case, then it might be that in order to run Linux you will need to completely blank the harddisk first.