I have, for quite some time, a dual boot setup on my MacBook Pro with MacOS X (minimal setup for emergencies) and Ubuntu (the system I use daily). I have ReFIT 0.14 installed. I am running this setup on this machine for well over a year without an issue.
This morning I rebooted my MacBook and when it came back up, it showed the ReFIT menu but the Linux entry would not work. When selecting it, all I would see is the penguin, and nothing else happens. Booting MacOS X works fine.
I have access to the file system via fuse-ext2 on MacOS, and looking at the logs the laptop booted the last time on October 22nd. The only system update afterwards was this morning, but only for git, some xserver input module, ruby and macfanctld. No updates to grub or the kernel.
I am a bit at a loss what to do, any pointers are greatly appreciated. I already reset the NVRAM and the SMC. I also tried syncing the partitions but it refused to do so due to "analysis inconclusive" (the MBR partition table shows two additional partitions at the end (Linux root and swap) that the GPT table does not, however the GRUB partition is shown in both).
Until I read your last sentence, I thought this sounded like your GRUB installation had gone south; however, if your MBR partition table is showing partitions that aren't present in the GUID Partition Table (GPT), then that sounds like some serious partition table corruption. To diagnose this, both GPT and MBR data is required. You can get this in one go from the Boot Info Script. Run it from an emergency Linux boot and post a link to the RESULTS.txt file that it produces. Be aware that this is likely to be a highly system-specific problem.
OTOH, if I've misunderstood, it could be that you need to re-install GRUB on the computer, or install another boot loader. I generally recommend using an EFI boot loader on Macs, especially if they don't boot Windows, since this enables you to do without all the flakiness associated with hybrid MBR configurations. OTOH, some models don't do well booting Linux in EFI mode because Linux doesn't correctly activate all their hardware (sometimes including video hardware). The only way to know for sure is to try it. I've written a Web page on EFI boot loaders for Linux, so you can peruse it and decide which one you want to install. Since rEFIt is already installed, you should just be able to drop the files into a subdirectory of the EFI directory on your ESP or the OS X boot drive (as in EFI/elilo or EFI/grub) and rEFIt should pick them up. (An exception is if you want to use the Linux kernel's EFI stub loader; for that, you should replace rEFIt with rEFInd.)