Abra um terminal e digite os seguintes comandos:
sudo -i
apt-get clean
cd /var/lib/apt
mv lists lists.old
mkdir -p lists/partial
apt-get clean
apt-get update
Isso renomeará sua pasta "list" para "list.old" para fins de backup e, em seguida, será recriada.