Parece que você ainda não atualizou suas listas de pacotes, isso está faltando no link que você deu -
sudo apt-get update
Isso deve fazer o download dos arquivos de lista dos repositórios em /etc/apt/sources.list
, para que apt-get install
saiba quais pacotes devem ser procurados.
Note também que você deve fazer isso regularmente, pois o repositório mudará com o tempo. Em particular, faça isso antes de instalar o software, se ele não tiver sido feito por um tempo!