Aqui está a solução (mais fácil):
Digite os seguintes comandos no terminal:
$ sudo -i
# apt-get clean
# cd /var/lib/apt
# mv lists lists.old
# mkdir -p lists/partial
# apt-get clean
# apt-get update
Créditos: ubuntugeek.com
Editar:
Se o erro ocorrer novamente (talvez após alguns dias / meses), abra o Nautilus como root > navegue até var/lib/apt
> elimine a pasta "lists.old" > abra a pasta "listas" e exclua a pasta "parcial". Agora, execute os comandos acima mencionados novamente.