Acabei de me deparar com este problema de dependências não cumpridas ao tentar fazer uma "atualização do apt-get", mas também tive o problema adicional de / boot ter ficado sem espaço.
Alguns erros que fornecem pistas de que seu / boot está sem espaço:
gzip: stdout: não há espaço disponível no dispositivo
Nenhum relatório de relatório escrito porque a mensagem de erro indica um erro de disco cheio
Isso significava que o apt-get era indefeso, com "sudo apt-get install -f" e "sudo apt-get autoremove" não funcionando.
No final, o link na resposta de Justin forneceu a solução:
1) Verifique quantos kernels antigos genéricos que você instalou:
find /boot -type f -regex "^.*-generic"
2) Se mais de 2, limpe manualmente os antigos
sudo find /boot -type f -regex "^.*XX-generic" -delete
Substituindo XX pelo número do kernel antigo que você deseja remover (por exemplo, localizar / boot -type f -regex "^. * 24-generic" -delete) deixe os últimos dois kernels (os dois números mais altos).
3) Agora você tem espaço para corrigir as dependências não atendidas:
sudo apt-get -f install