Acho que o espelho que você usa atualmente está quebrado ou não totalmente sincronizado.
Basta alternar os espelhos com o Synaptic ou usar um editor de texto.
Com o Synaptic, você pode fazer a troca das opções.
Se você quiser usar um editor de texto, faça o seguinte:
1) Abra um terminal
2) Tipo: gksu gedit /etc/apt/sources.list
3) Editar - > Substituir todos.
4) Substitua todas as cadeias de país, para um país anterher.
Como no meu caso, eu tenho "hu.archive". por padrão, que é o pior espelho que já vi. Então eu vou lá depois de cada instalação, e mudo a parte "hu" para "de" como na Alemanha. Então parece com isso: de.archive.
(Todas as linhas onde há um prefixo do país).
Depois disso, faça um apt-get update
e tente a atualização (novamente).