At first I thought that was the problem, but then I saw that booting from the cdrom was one of the boot option in the BIOS (but as I said I cannot modify this option to put it "first").It's entirely possible that a machine that old is not capable of booting from optical.
I don't remember *when* it was, exactly, but I do remember a time when booting from a CD without the need for a boot floppy was new and amazing.
Could there be a discrepancy between the BIOS and the machine possibilities ?