Eu encontrei uma solução. Parece que meu / boot estava cheio. Eu encontrei em outros fóruns pessoas resolvendo isso aumentando o tamanho, mas eu adotei uma abordagem diferente e menos agressiva limpando com:
sudo apt-get autoremove
Depois disso, precisei atualizar com:
sudo apt-get upgrade
Agora que consegui atualizar, consegui instalar qualquer pacote necessário.