I've installed rh9 on a box of mine that had previously happily dual booted rh73 and rh80. After installing rh9 and adding the appropriate entries to /etc/grub.conf for rh73 and rh80, I can no longer boot into these older OS's, with grub giving an error: Invalid executable type. Some details: all 3 redhat's share a common /boot partition, with grub being installed to the boot sector of this partition. I'll go try re-installing rh80's version of grub to the boot sector, and see if that helps...
Can you attach your grub.conf as well as the output of running file on each of the other kernels you're trying to boot?
Forget it, my bad. Multiple stupid typos in grub.conf (after staring at it for 20-30 minutes) made some boot images not work.