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.