Eu tive o mesmo problema, acabou sendo falta de espaço em / boot:
Então, eu fui ao / boot e encontrei uma tonelada de kernels antigos:
Eu apaguei todos, exceto os últimos três (apenas para ter alguns fallback :) e executei o comando apt-get install novamente. Trabalhei dessa vez.
Espero que isso ajude, PS
edite - Eu colei alguns resultados, mas eles não foram formatados corretamente, então eu os removi.