For some reason, with the Fedora series, I also have problems booting after a fresh installation. I haven't used FC4, but I suggest trying a fresh install again. Otherwise, I have a last resort idea if you are interested which has always worked for me
The short form:
I just installed Fedora Core4, but the system won't boot. I get:
DISK BOOT FAILURE, INSERT SYSTEM DISK AND PRESS ENTER
The long form:
I have 3 SATA hard drives labelled by fedora as sda, sdb,sdc. The driver used for intall is sata_nv.
Installation went smoothly without any errors. But it won't boot.
I tried fedora core 3, same problem.
Grub is installed, and the contents of grub.conf, fstab, mtab are shown below.
/etc/mtab
/dev/VolGroup00/LogVol00 / ext3 rw,defaults 0 0
/dev/sda1 /boot ext3 rw,defaults 0 0
/dev/proc /proc proc rw,defaults 0 0
/dev/sys /sys sysfs rw,defaults 0 0
/boot/grub/grub.conf
# grub.conf generated by anaconda
#
# Note that you do not have to rerun grub after making changes to this file
# NOTICE: You have a /boot partition. This means that
# all kernel and initrd paths are relative to /boot/, eg.
# root (hd0,0)
# kernel /vmlinuz-version ro root=/dev/VolGroup00/LogVol00
# initrd /initrd-version.img
#boot=/dev/sda
default=0
timeout=5
splashimage=(hd0,0)/grub/splash.xpm.gz
hiddenmenu
title Fedor Core4 (2.6.11-1.1369_FC4)
root (hd0,0)
kernel /vmlinuz-2.6.11-1.1369_FC4 ro root=/dev/VolGroup00/LogVol00 rhgb quiet
initrd /initrd-2.6.11-1.1369_FC4.img
/etc/fstab
/dev/VolGroup00/LogVol00 / ext3 defaults 1 1
LABEL=/boot /boot ext3 defaults 1 2
/dev/devpts /dev/pts devpts gid=5,mode=620 0 0
/dev/shm /dev/shm tmpfs defaults 0 0
/dev/proc /proc proc defaults 0 0
/dev/sys /sys sysfs defaults 0 0
/dev/VolGroup00/LogVol01 swap swap defaults 0 0
I have samples of the same files from fedora core 1 if you would like to see them.
Thx.
Richie.

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic