The solution here turned out to be updating the microcode (firmware) for the CD-ROM. Note that this is not the firmware for the machine itself. I had already updated that first thing.
For whatever reason, the 40X CD-ROM drive in my machine would boot from the 4.3.3 media, but not from the 5.x media. This was a known (but not well-documented) issue and much Googling led me to try updating the microcode on the CD-ROM drive. This worked and I can now boot from 5.x media.
The microcode download site is:
In the last section (Other Code) you have to download software called Genucode. This software + the microcode for your device lets you update the code from 4.x. You can then install 5.x.
Word to the wise: when you run the Genucode binary, it will ask for a password. It states that it is contained in the license agreement. It is, in fact, at the top of the downloads page in red, NOT in the actual license agreement page for the fixes.
Hope this helps someone else. I wasted many hours looking for this solution.