Primeiramente, tente este comando (do terminal) como root:
rm -rf /var/cache/apt/*.bin
E tente apt-get upgrade
novamente. Se o problema persistir, você provavelmente encontrou um bug. Vá para o bug do launchpad e relate seu problema. Lembre-se de incluir detalhes como a versão do servidor Ubuntu ou qualquer outra informação relevante.
Obrigado!