O meu problema é semelhante a este . Eu removi o Windows e partições de recuperação no meu ultrabook para criar mais espaço para o Ubuntu Linux. A partição de inicialização EFI criada pelo instalador do Ubuntu ainda está lá, e eu encontrei uma opção "ubuntu" no menu de inicialização EFI que inicia o GRUB e o Ubuntu sem problemas, como antes.
Infelizmente, essa opção agora desaparece após cada inicialização e recebo um erro "Sistema operacional não encontrado" do meu BIOS. Para inicializar o sistema novamente, eu preciso remover manualmente a entrada "ubuntu" existente usando efibootmgr (de um live CD), que de alguma forma ajuda a BIOS a encontrar o Ubuntu novamente. Executar grub-install de dentro do Ubuntu também funciona. O problema é que esses hacks precisam ser feitos todas as vezes para garantir que o sistema seja inicializável na próxima vez que eu reiniciar.
Como posso tornar a opção permanente? Por que está sendo apagado? Infelizmente, abandonar a UEFI estúpida e reinstalar o sistema no modo herdado não é uma opção no momento.