I'm not a Mac person, but Dave hit this a few days ago on a brand shiny new Mac Mini and it was somewhat traumatic. Since none of the pages we found were helpful, here's my contribution to the googosphere.
Ubuntu through Intrepid (supposedly this will be fixed in Jaunty; we didn't test it) have a major bug in their installer which will render Macs unable to boot -- even off a CD. (I should mention that the problem isn't limited to Ubuntu -- I did see a few Fedora discussions while I was googling.)
What happens is that in the grub install stage, gparted writes the partition table (even if you didn't repartition) to the disk in a format that's incompatible with the Mac boot loader.
For the gory details, it's Bug 222126: Partition Table is cleared during install on Intel Macs.
There's some discussion in a couple of Ubuntu forums threads: 8.04 won't boot and Intel Macs with Hardy 'no bootable devices' and all of them point to an open source Mac app called rEFIt (yes, it's supposed to be capitalized like that). But Dave had already tried to install rEFIt, he thought, unsuccessfully (it turned out it was installed but wasn't showing its menu properly, perhaps due to an issue of his Apple keyboard not properly passing keys through the USB KVM at boot time. Ah, the Apple world!)
Anyway, none of the usual tricks like holding Alt or C during boot were working, even when he took the KVM out of the loop. After much despair and teeth gnashing, though, he finally hit on the solution:
Cmd-Option-P-R during boot to reset the Parameter RAM back to factory defaults.
We still aren't clear how the Ubuntu installer managed to change the Parameter RAM. But a couple of iterations of Cmd-Option-P-R cleared up the Mini's boot problem and made it able to boot from CD again, and even made rEFIt start showing its menu properly.
There's one more step: once you get the machine straightened out enough to show the rEFIt menu, you have to right-arrow into rEFIt's partition manager, hit return, and hit return when it asks whether to synchronize the partitions. That will reformat the incorrect gparted-format partition table so the Mac can use it. (And with any luck, that is the last time that I will EVER have to type rEFIt!)
(Though a better way, if you could go back and do it over again, is to click the Advanced button on the last screen of the Ubuntu live installer, or else use the alternate installer instead. Either way gives you the option of writing grub to the root partition where you installed Ubuntu, rather than to the MBR, leaving you much less horked. You'll still need to rewrite the partitions with rEFIt (grumble, I knew I wasn't quite through typing that!) but you might avoid the Parameter RAM scare of not being able to boot at all.)
That's the story as I understand it. I hope this helps someone else who hits this problem.
[ 23:49 Apr 05, 2009 More linux/install | permalink to this entry | ]