Se sua partição / boot estiver sem espaço para o novo kernel, ela falhará. Um apt-get autoremove'
normalmente apaga a menos que você tenha um kernel preso em meio a uma instalação. Nesse caso, você precisa criar espaço manualmente e executar apt-get -f install
para concluir a instalação.
Gostaria de saber se, na sua situação, você não teve um kernel instalado e talvez tenha limpado algum espaço no seu processo. Acho que já vi isso uma vez, não é comum. Normalmente isso só quebra assim parabéns!