Isso pode funcionar.
sudo dpkg --clear-avail
sudo apt-get update
Também pode não. Você também precisa verificar o seu sistema de arquivos em busca de erros, e certifique-se de usar apenas os repos que são para a sua versão do Ubuntu.
Eu começaria com os comandos acima, então se isso ainda não funcionar, dê uma olhada aqui para restaurar seu banco de dados apt.
Você também pode tentar (muito perigoso)
sudo mv /var/lib/dpkg/updates /root/
sudo apt-get update
sudo mkdir /var/lib/dpkg/updates
sudo chmod 755 /var/lib/dpkg/updates
Supondo que você está de volta, você pode remover a cópia das atualizações em /root/updates