Graças a @Panther, consegui consertar isso. Parece que o problema foi causado por uma partição de inicialização completa. Então o apt-get não funcionou mais. De acordo com o link , consegui remover kernels antigos não usados com este comando:
dpkg --purge $(dpkg -l linux-{image,image-extra,headers}-"[0-9]*" | awk '/^ii/{print }' | grep -ve "$(uname -r | sed -r 's/-[a-z]+//')")
O comando uname -r
agora está mostrando apenas o kernel ativo atual e tudo funciona bem agora.
Para listar todos os kernels instalados, você pode digitar:
dpkg --list | grep linux-image