I haven't used this in years, but in the past when I was trying to set up a non-mac OS on that kind of machine the issue was with getting the EFI bootloader to boot the OS. That error also makes me think that it's something similar.
You might look into something like
rEFInd which is a fork of the old rEFI project, although I'm not sure what hardware is supported on those older macs.