Well, as suggested by various people, I booted the system into rescue mode using the install cd. Once booted, I chroot'ed, then ran:
This command did not return any errors. All output looked successful and normal from my experience on single-disk systems.
/boot/grub/devices.map, fdisk -l, and grub tab expansion output all confirm that /dev/sda is indeed (hd0), and root is definately (hd0,0).
By the way, I also verified that /dev/sda1 is bootable, and that /dev/sdb1 is not bootable.
Now, when I boot the system, instead of getting a grub stage 2 error, I get a grub stage 1.5 error. Does this help anyone further diagnose the problem?