I had this exact problem when trying to set up a multi-boot system with 2 x Fedora linux and FreeDOS.
Not sure if the underlying problem is actually a bug in grub, but its the same in Fedora Core 1 and in Redhat 9. You can work around this problem as follows for two linux systems ........
Here the second system was added after main system, main system is multi partition, second system is a single partition. During second install added config to grub to hopefully boot original system.
My config as follows:
Main System has /boot in /dev/hda4, root in /dev/hda5, others elsewhere
Second System is entirely in /dev/hda6
The second system boots ok, the original system can be selected from the menu, but the 'invalid or unsupported executable format' message appears.
The implication of this is the MBR on the root disk points to the new system.
Solution I used was to boot from diskette (you DO have a boot diskette for one of the systems I hope) to get the original system up. At the boot prompt 'boot: linux root=/dev/hda5'. Had a look at the original systems /boot/grub/menu.lst to find out exactly how it boots. Mounted the new systems root on a temporary mount point. Then modify the /boot/grub/menu.lst for the second system to point directly to the kernel
This is the resultant config file - note the paths to cope with the fact that on main system files are on a separate filesystem.
# grub.conf generated by anaconda
# Note that you do not have to rerun grub after making changes to this file
# NOTICE: You do not have a /boot partition. This means that
# all kernel and initrd paths are relative to /, eg.
# root (hd0,6)
# kernel /boot/vmlinuz-version ro root=/dev/hda7
# initrd /boot/initrd-version.img
title Mini Fedora Core (2.4.22-1.2115.nptl)
kernel /boot/vmlinuz-2.4.22-1.2115.nptl ro root=LABEL=/1 hdc=ide-scsi
title Main Fedora Core
kernel /vmlinuz-2.4.22-1.2115.nptl ro root=LABEL=/ hdc=ide-scsi rhgb
Hope this helps.