Pode ser um par de coisas.
Fontes não atualizadas
Embora a área de trabalho do Ubuntu faça isso ocasionalmente, muitas vezes é necessário atualizar suas fontes antes de instalar os pacotes, para garantir que o gerenciador de pacotes obtenha alterações recentes nos pacotes disponíveis.
Você faz isso com o botão "Verificar" no gerenciador de atualização ou com sudo apt-get update na linha de comando.
Problema temporário com o espelho
Ocasionalmente, dependendo do espelho que você está usando, pode haver problemas temporários em que o espelho diminui temporariamente ou tem outros problemas.
Você encontrará frequentemente que, se tentar a mesma coisa novamente mais tarde, os problemas serão resolvidos. Ou, se for algo importante, tente um espelho diferente.