Após muita procura de soluções, também me encontrei em situação semelhante. A solução da AndrewM também não funcionou para mim. O Mac está em puro EFI (não-híbrido), puro Linux de 64 bits.
Algumas dicas a serem feitas: 1) Existem dois projetos, rEFIt e rEFInd. 2) Você pode instalar ambos e descobri que eles vão se detectar e permitir que você inicialize um do outro.
Aqui está o que finalmente me trouxe de volta ao Linux após a atualização do Mavericks ... Faça o download do último link rEFind (atualmente 0.7. 4) e emita este comando do OS X:
sudo ./install.sh --alldrivers
Acabei com um longo menu de todos os meus kernels do Linux e consegui inicializar diretamente no Ubuntu / Debian sem o menu GRUB. Agora, pelo menos, posso entrar no Linux e refazer o GRUB e ver as configurações do EFI.