A situação mais provável é que você precise atualizar suas fontes por algum motivo, com
sudo apt-get update
Também é possível que suas fontes não estejam configuradas corretamente. Você pode configurá-los no gerenciador de atualização. Eles estão localizados no arquivo /etc/apt/sources.list - se você continuar tendo problemas, cole a fonte desse arquivo aqui.