Eu estava tendo esse problema e depois de muito tempo procurando o que estava causando t, descobri que o gerenciador de software não estava atualizando o initramfs deixando o estado de inicialização quebrado. Mas isso só acontece com algumas pessoas. Eu não sei porque.
Tente atualizar o inirtramfs:
sudo update-initramfs -u
Diga-me se funcionou.
EDIT : Parece que é um bug, não no gerenciador de atualização, mas no kernel. link