Well, thanks for the info guys. I managed to get it done. Below is an account of my actions, just in case someone looks for the same info.
1) I made a bootdisk using the following command:
"mkbootdisk --device /dev/fd0 2.4.18-27.8.0"
This created a bootdisk tailored to my system. It stored enough information on the disk that I could boot to my Linux system no matter what the bootloader looked like.
2) (Re)installed Windows. As expected, this overwrote the MBR so that the system only booted to Windows. Didn't have to do an fdisk /mbr, as it just did it by itself. Finished the entire installation. Windows stable(for now).
3) Booted of the Linux bootdisk.
4) Did a "grub-install /dev/hda".
5) System Up and Running
Of course, your mileage may vary, but this worked for me.
Thanks to all the people that replied.