O problema é que você excluiu recursivamente /var/lib/apt/lists
, que também excluiu o diretório parcial. Então, recriar o diretório deve resolver o problema:
sudo mkdir -p /var/lib/apt/lists/partial
sudo chmod 755 /var/lib/apt/lists/partial
Além disso, é possível que o espelho que você está usando tenha problemas. Selecione outro espelho e atualize novamente.