Isso é mais um palpite do que uma resposta real.
Se você atualizar as listas de pacotes, receberá algum aviso ou erro?
sudo apt-get update
-- go through and check for warnings
E as fontes são boas?
cat /etc/apt/sources.list
-- check if something important is out-commented.