<< fdisk /mbr would have cleaned grub off the MBR without all that work, if you had only asked.
And maybe I'm strange, but I don't think Linux is to blame here. >>
Actually, it might be Redhat's fault. When I installed Redhat 7.2 (dual boot with grub) redhat screwed up my grub config file (the windows 2000 part).
For some reason, it seemed to get my win 2k boot partition wrong.
In any case, I was able to get the dual boot working again without having to format. I think your best bet might have been pressing
e for edit (or whatever option it is) on the grub boot screen and then edit the rootnoverify (hd0,1) line like nothinman said. But doing it in the boot menu gives you the chance of chaning the partition number until you get it right.