Na verdade eu resolvi esse problema no mesmo dia, o problema foi com o arquivo archive.ubuntu.com mais próximo (Ubuntu Archive Server) Eu mudei todas as suas instâncias (13 ocorrências no meu caso) para us.archive.ubuntu.com e funcionou. O arquivo de configuração onde eu mudei essa configuração foi /etc/apt/sources.list.
Editar : Recentemente eu encontrei outra pergunta no askubuntu, a resposta aceita para esta pergunta também é uma boa solução para este problema se você não quer mudar o endereço do arquivo archive.ubuntu.
Aqui está essa pergunta.