Se você excluir todo o /var/lib/apt/lists hierárquico, deverá criar o diretório partial abaixo dele:
sudo mkdir -p /var/lib/apt/lists/partial
Além disso, verifique se todas as permissões estão definidas:
sudo chmod -R 644 /var/lib/apt/lists
sudo chown -R root:root /var/lib/apt/lists
Então, apt-get update novamente.