Pode ser que sua cópia do GRUB esteja danificada. Eu tenho duas sugestões:
- Use Reparo de inicialização de um disco de emergência para reinstalar o GRUB.
- Use o meu gerenciador de inicialização do rEFInd (a unidade flash USB ou a versão do CD-R) para inicializar em seu computador sistema. Você pode então fazer um
sudo grub-install /dev/sda
ou instalar o pacote rEFInd PPA ou Debian para uma solução permanente.
Observe que a segunda opção funcionará somente se a Inicialização Segura estiver realmente desativada. Parece que você não está 100% certo de que está desabilitado e, de fato, essa é outra possibilidade - se uma atualização instalou um Shim assinado incorretamente, ou se seu firmware é misto sobre suas assinaturas de inicialização segura, pode ser que seu sistema não gosta de um Shim atualizado. Nesse caso, voltar ao firmware e desabilitar o Secure Boot é a solução adequada, pelo menos a curto prazo. Eu mostro vários exemplos de como desabilitar o Secure Boot em esta página minha, se você precisar exemplos. (Infelizmente, as interfaces de usuário para fazer isso não são padronizadas).