Just finished ~20h to get Ubuntu 12.10 running on a 2011 MacBook Air. The problem was that rEFIt does not work if your main partition is encrypted using FileVault2 (OSX' Disk Encryption).
The solution: Install rEFIt in the hidden main system partition like documented here. Install Ubuntu 12.10 (64bit) with boot manager on EFI boot partition.
What I also tried:
- Installing rEFIt on another HFS+ Partition, no luck doesn't show up when booting and Alt pressed
- Ubuntu 12.04 Mac - AMD64 with boot grub partition as documented in the Wiki, no luck doesn't show up
Update: The bootloader seems to be removed after a couple of reboots :/