One shot-in-the-dark solution is to replace rEFIt, which has been abandoned for over five years, with its maintained fork, rEFInd. (Note: I'm rEFInd's maintainer.) If you want to play it safe, you can try rEFInd risk-free by using its USB flash drive or CD-R version (both available from the downloads page). rEFInd may help because it can detect and launch Linux kernels directly, whereas rEFIt relies on an EFI or BIOS-mode boot loader -- and based on the error message, it sounds like it's trying to launch Linux in BIOS mode but is running into problems with the boot loader.
That said, you've got at least one other symptom that disturbs me a bit: the
gptsync issue, which might denote a serious partition table problem. OTOH, that could be a
gptsync bug or some minor issue that's not worth worrying about. In any event, if you want a more thorough diagnosis, I recommend booting a Linux live session and running the Boot Info Script. (It's available in the
boot-info-script package in Ubuntu.) This will generate a file called
RESULTS.txt. Post that file to a pastebin site and post the URL to your document here. That will give us some solid diagnostic information to help us figure out what's going wrong.
It looks like you no longer have a hybrid MBR, which would explain why rEFIt has stopped booting Linux. Your computer seems to have a BIOS-mode GRUB, which would require a hybrid MBR to work correctly. Before you try to fix that, though....
rEFInd, unlike rEFIt, enables you to boot Linux kernels directly. You should see both the old Linux penguin icon that rEFIt showed you and a new Ubuntu icon. The latter should launch the Linux kernel directly, and it should work without a hybrid MBR. If that works, I recommend you use it and ignore the old BIOS-mode Linux icon. (You can remove it, too, but that will require more effort.)
If you don't see an Ubuntu icon, you might need to install an EFI driver for ext4fs. This driver comes with rEFInd, and should have be installed automatically if you used
install.sh without options, but it might not have been for some reason, so doing it manually should fix things. See the rEFInd drivers page for more on this subject.
If the Ubuntu icon exists but doesn't work, please post details of what's not working.
If you want to boot in BIOS mode using GRUB, you'll need to create a new hybrid MBR. I don't see any reason offhand why
gptsync isn't working for you. You might give
gdisk a try instead. (This program comes with Ubuntu and is available for OS X.) See the
gdisk documentation on hybrid MBRs for information on how to create a hybrid MBR. In your case, it shouldn't really matter what partition(s) go into the hybrid MBR, since neither OS X nor Linux uses the hybrid MBR; you need it just to activate BIOS support in your Mac's EFI.