O problema parece ser que há algo errado com os de
servidores (persistentemente: veja a idade da pergunta!). Eu mudei todas as entradas de de
no /etc/apt/sources.list
para os nl
servidores e atualiza bem agora.
Parece que, depois de atualizar de um servidor diferente, você pode reverter para o seu servidor local. As pessoas agradáveis do ubuntu-espelhos não conseguiram explicar isso, mas funciona.