Como você descobriu, desabilitar o Secure Boot corrige o problema. Meu palpite é que você tinha desativado antes e de alguma forma acidentalmente habilitado ou você estava usando uma versão do GRUB habilitado para Secure Boot antes e uma atualização de software instalou um GRUB não assinado ou alterou o caminho de inicialização de uma forma que ignorou o programa shim ( que é o que o Ubuntu usa para suportar o Secure Boot).
Outra opção é adicionar suporte à Inicialização Segura de maneira mais geral. Se o seu primeiro gerenciador de partida for o rEFInd, você poderá ler a documentação de inicialização segura do rEFInd para obter detalhes sobre como fazer isso funcionar com inicialização segura. Infelizmente, o Ubuntu ainda não vem com uma versão do shim habilitada para MOK, então você precisará instalar outra versão do shim e adicionar a chave pública do Ubuntu à sua lista MOK. Isso é possível, e nem é tão difícil, mas envolve o uso de várias ferramentas de linha de comando e o acompanhamento de instruções com bastante precisão. Note que o Ubuntu adicionou suporte a Boot Seguro com a versão 12.10. Eu notei uma tag 12.04 em sua pergunta, então se você estiver usando 12.04, seus kernels quase certamente não serão assinados, o que irá complicar este uso mais completo do Secure Boot. No geral, provavelmente é melhor deixar a inicialização segura desativada; Eu menciono essa alternativa caso você tenha motivos para ativá-la.