Tente atualizar seus pacotes com sudo apt-get update antes de instalar.
Não tenho certeza, mas acho que o feed de banner não tem nada a ver com o status das suas listas, por isso há uma chance de você ver o software no banner que não foi atualizado na sua lista de pacotes.
Se isso não funcionar, mude o servidor do que você tem no momento para servidor principal e tente atualizar novamente.
Se a atualização das suas listas e a alteração do servidor não funcionarem, você deve informar isso como um bug.