When I installed Mandrake 8.2 the first time I got the same error, but I'm not using it anymore, and I don't recall what was the problem.
It could be yaboot and not the Linux partition that causes the problem. So you could try and override yaboot by choosing a boot partition in either OSX or OS9. If the Linux partition can be seen from the startdisk panels it may be bootable too. But remember, once you touch the startdisk panels yaboot will be wiped out. It can be reactivated again by starting up with open firmware, though.
Not much of an answer, I know.