Tente o seguinte:
cd /var/lib/apt
sudo mv lists lists.old
sudo mkdir -p lists/partial
sudo apt-get update
Isso redefinirá o cache do zero.
Veja se isso resolve o problema. Se não, você pode reverter as alterações feitas acima, fazendo o seguinte:
cd /var/lib/apt
sudo rm lists
sudo mv lists.old lists
sudo rm -r lists/partial
Nota: Se a primeira parte não funcionar, o segundo comando ( sudo rm lists ) pode falhar, tudo bem.