Verifique se as informações dos pacotes foram baixadas corretamente. Na linha de comando isso pode ser feito com
sudo apt-get update
Nos gerenciadores de pacotes da GUI, acredito que deve ser uma opção como pacotes de atualização ou algo assim, que faz o mesmo.