After a lot of searching for solutions, I also found myself in similar situation. AndrewM's solution did not work for me either. The Mac is on pure EFI (non-hybrid), pure 64 bit Linux.
A couple points to make: 1) There are two projects, rEFIt and rEFInd. 2) You can install both and I have found that they will detect each other and let you boot one from the other.
Here is what finally got me back into Linux after Mavericks upgrade... Download the latest rEFind http://www.rodsbooks.com/refind/ (currently 0.7.4) and issue this command from OS X:
sudo ./install.sh --alldrivers
I ended up with a long menu of all my Linux kernels and was able to boot directly into Ubuntu / Debian without GRUB menu. Now at least I can get into Linux and rework the GRUB and look at EFI configurations.