Bem, eu posso ser um novato no Ubuntu, mas sou um novato persistente no Ubuntu e sabia que, se continuasse escolhendo o tempo suficiente, eu descobriria.
Encontrei um artigo muito antigo (2008) descrevendo uma situação semelhante e imaginei, por que não, tentar. E funcionou.
sudo dpkg --audit me deu isto: Os pacotes a seguir foram descompactados, mas ainda não configurados. Eles devem ser configurados usando o dpkg --configure ou o configure opção de menu no dselect para eles funcionarem: alacarte easy ferramenta de edição de menu do GNOME Ligações python-gi do Python 2.x para bibliotecas de introspecção de objetos
Os seguintes pacotes são apenas parcialmente configurados, provavelmente devido a problemas configurando-os pela primeira vez. A configuração deve ser repetida usando dpkg --configure ou a opção de menu de configuração no dselect: capacidades extras do virtualbox-ext-pack para o VirtualBox, downloader.
Eu então executei: sudo dpkg -r virtualbox-ext-pack que levou a isto: (Lendo banco de dados ... 745263 arquivos e diretórios atualmente instalados.) Removendo o virtualbox-ext-pack (5.0.36-0ubuntu1.16.04.2) ... 0% ... 10% ... 20% ... 30% ... 40% ... 50% ... 60% ... 70% ... 80% ... 90% ... 100% Desinstalado com sucesso "Oracle VM VirtualBox Extension Pack". Executei com sucesso a limpeza do pacote de extensões
E finalmente o sudo apt-get update que finalmente terminou completamente.