Você precisa atualizar suas listas de pacotes.
Executar:
sudo apt-get update
Em seguida, tente novamente. Isso consertará tudo.
Você vê, quando desenvolvedores de software do Ubuntu gravam seus softwares, eles os enviam para os servidores do Launchpad, onde eles compilam e processam o código. Uma vez que o código tenha sido compilado com sucesso, o novo pacote substitui o pacote antigo, e as listas de pacotes são atualizadas para refletir essa mudança.
Note que são apenas as listas de pacotes no servidor deles , não no seu computador. sudo apt-get update
obtém as informações mais recentes dos pacotes dos servidores, no ponto em que seu computador os processa.
O comando sudo apt-get upgrade
verifica as listas de pacotes (aquelas armazenadas no seu computador) e compara o software na lista de pacotes com as versões reais que você instalou. Se algum de seu software tiver uma versão mais recente do que a listada na lista de pacotes, ele será baixado e instalado.
A execução de sudo apt-get install <PACKAGE>
verifica sua lista de pacotes para esse software. Se encontrado, ele é baixado e instalado.
(note que o pacote lista não contém o software em si - apenas o nome, a versão e a URL para baixar o software).
Enfim, espero que meu pequeno discurso tenha ajudado você a entender o sistema de pacotes do Ubuntu um pouco melhor!