Being a new Dad doesn't provide me much time to research this stuff on my own time anymore, so I had recently resigned myself to accepting having to boot into rescue mode to get the system up and running past GRUB.
Then today at work I was investigating block level alignment to VMware guests running RHEL with the storage back-end (NetApp SAN). I found a document that walks one through a utility that is a part of the ESX host utility kit from NetApp called MBRAlign. The document goes on to say that after you align Linux guests, grub likely needs to be reinstalled and they provided detailed steps - ding ding ding --> yay! This is exactly what I need. I was trying to fix my issue with "grub-install" and tried identifying the whole (hd0,0) thing with every possible combination I knew possible each time I had to reboot (due to power outage or whatnot). Then, I found this document and found the missing steps, which are (after booting into rescue mode and chrooting the system):
1 - grub
2 - root (hd0,0)
3 - setup (hd0)
4 - quit
This didn't work the first time, I tried something like hd1,0 in the second step and it worked! It got me to the boot loader to the point where I could see the kernels, but it still failed to boot however after a quit edit there to point it at hd1,0 instead of hd2,0, it works! Now I just need to make that change persistent in /boot/menu.lst and I am good
So the issue was that grub couldn't find the second part of the loader (or whatever).
yay!!! So happy
Did NOT want to reinstall and didn't have time to figure it out on my own, hopefully someone else in this situation can make use of this post and benefit them