If, after re-installing Grub, you see the Grub boot menu but are unable to boot Linux because your vmlinuz and initrd files are missing, you have a bigger problem than Grub. The vmlinuz file (kernel) and initrd are accessed by Grub and Grub is done. You won't be able to boot without these two files. I would guess that they were deleted/moved (etc) somehow, during your format?
I guess the good news is that there is nothing wrong with Grub. You need to re-install the vmlinuz and initrd files from your Redhat. Use your Linux CD and enter 'grub' to get grub prompt (grub>), then enter commands:
to see if the files are there and where they are. What is the output of 'fdisk -l' command? How many drives/partitions do you have?