Eu tive esse problema no passado e tenho visto resultados positivos dos seguintes comandos.
sudo apt-get clean
sudo apt-get autoremove
e, em seguida, o comando abaixo que eu li era tudo o que era necessário para algumas pessoas.
sudo apt-get install
Referências: