I installaled, 2 and 1/2 year ago, RedHat Linux 5.0 on six old Olivetti, with 8MB RAM and 400MB HDD (actually it was an upgrade from Slackware). Everything was OK, including a NIS server, needed to have my ~30 students entered once. Since, when upgradind to 5.1, 5.2, 6.0 (which I payed for), I had to cheat: boot disks greater than 5.0 gave "boot failed" messages. I installed release 5.1, and now 6.0 with 5.0 boot.img! I first thought it was a RAM issue, but upgrading to 32MB RAM didn't change anything. I would be very interested to understand. Please excuse my poor english.
corrected component
Couldn't really upgrade to 6.0: Redhat Kernel 2.2.5 is compiled for Pentium. But this has nothing to do with boot disk.
This is most likely a bug with syslinux on your BIOS. Please try creating a lilo boot floppy or using loadlin.