Tente isto:
sudo cp -r /var/lib/apt/lists /var/lib/apt/lists.bak
sudo rm -vf /var/lib/apt/lists/*
e depois novamente
sudo apt update
Diga-nos se funciona. A localização de /var/lib/apt/lists
contém arquivos deb baixados automaticamente.