What kind of CD's are you using? I mean, are the factory pressed, CD-R or CD-RW? How many different disks have you tried? All I've read about so far is supergparted and Puppy Linux, is there anything else?
Your supergparted disk seems to boot OK, and you can edit the HDD partition(s) with it, right? So your hardware is working. Must be a difference in the disks themselves. Have you been able to boot anything other than gparted recently?
The way a computer boots (with the boot order you mention), is it will look for boot info on the first device (CD disk), if it finds none it moves on to the next device, and so on down the list. So, a corrupt boot sector on the hard drive cannot prevent boot from a CD if the CD drive is ahead of the hard drive in the boot order. You could even physically remove the HDD from the machine, and still boot from CD's. That's one of the main features of Puppy, being able to use the computer when there is no hard drive.
Collection = T500 - R400 - X300 - X200 - T61 (14" WXGA+) - T61 (14.1" SXGA+) - T60 (15" SXGA+) - X40 - T43p - T43 - T42p - A30P - 600E