Error: partition table requires a separate partition for boot loader code (EFI issue)

Read the whole answer before following the instructions below.

In order to fix this issue you need to create an extra partition.

1. Install rEFIt or rEFInd¹ in Ubuntu.
2. Start Mac OS X.
3. Launch OS the Disk Utility application.
4. Make sure to have already resized your "Macintosh HD" partition so that you have room for the new partitions (~50 GiB is what I chose).
5. Restart using a Ubuntu Live CD.
6. Select "Try Ubuntu".
7. Start the application named GParted.
8. Create a new partition called "bootloader" with file system ReiserFS. I made this partition 500 MiB. I'm not exactly sure if the file system or size matters. According to Wikipedia BIOS Boot partition page, this partition can be as small as only 1 MiB.
9. Create a new linux-swap partition that's about 1 GiB. I called this one "swap".
10. Create an ext4 partition called "primary" using the rest of your unallocated space.

After following the instructions above, GParted should look similar to the following image. Keep in mind that I took this after installation. The labels for my linux-swap and ext4 partitions disappeared and the key/exclamation icons were added after installation by Ubuntu. Also, no need to set a bios_grub flag for the ResiserFS partition, this was also automatically added post- (or during-) installation.

Now that the partitions are set up, go back to the desktop, click on "Install Ubuntu 12.04" (this should also appear in the menubar on the left if it's not on the desktop), and follow along below

1. Go through the options (personalizing them however you like) until you get to the "Installation type" screen that asks you how you want to install Ubuntu.
2. On the "Installation type" screen, select "Something else" and continue (press "Install Now").
3. You'll now arrive at a window that lists all the partitions you have. Identify the "bootloader" partition (if the labels don't show, identify it by the device, type, or size columns) and double click on it.
4. A window that says "Edit partition" should popup. Select the option field next to "Use as:" and click on the value that says "Reserved BIOS boot area" (figure below). Press "OK."
5. Identify the ext4 partition you just created and bring up the "Edit partition" window.
6. Set the "Use as:" value to "Ext4 journaling file system," check the format option. Make sure to also set the mount field to /. Press "OK."
7. Go ahead and continue the process, personalizing the results as you desire.

From here, everything should work fine. Make sure to have rEFIt or rEFInd installed so that you can boot into Ubuntu later¹.

^{1. It turns out that if you get stuck while booting, instead of using a program like rEFIt and it's predecessor, you can just hold the alt/option key to boot into a partition/disk/whatever.}

The last time I checked (two or three releases ago), the "Mac alternate" version of Ubuntu was basically just the normal Ubuntu but stripped of its EFI boot options. This may seem peculiar, since Macs use EFI, but the problem is that the Mac's EFI is weird, and the standard Ubuntu installer had problems with the Mac's EFI. (I don't recall the precise nature of the problems, though.) Since Macs provide a BIOS compatibility layer, booting in that way makes sense; and when GRUB installs to a GPT disk using a BIOS boot mode, use of a BIOS Boot Partition (what the Ubuntu dialog box refers to as a "reserved BIOS boot area") is necessary. Hence, the dialog box asking for that area.

One option for how to proceed is to acquiesce with the request to create a BIOS Boot Partition. Ubuntu will then boot in BIOS mode, if all goes well. You can subsequently change the Linux boot mode by installing an EFI-mode boot loader. See my EFI-Booting Ubuntu on a Mac for one example of how to do this, and particularly the section entitled "Fixing the Installation."

Another option is to try using the standard Ubuntu installer rather than the Mac variant. You may need some help getting it to boot; it's possible that rEFInd will help with that, although I can make no promises. Once the installer is booted, you should ensure that it's running in EFI mode by looking for a directory called /sys/firmware/efi. If it's present, you've booted in EFI mode, and if it's not present, you've probably booted in BIOS mode and should try again.

Have you tried to choose /dev/sda1 as the place to install your bootloader? On the bottom of the custom installation menu, there is a place marked:

Device for bootloader installation

Choose /dev/sda1 from the dropdown menu.