Este foi um problema que não fazia sentido, além de algo estar corrompido. O Apt tem algumas ferramentas de limpeza integradas, que eu tentei:
apt-get check
Este comando é uma ferramenta de diagnóstico. Ele faz uma atualização das listas de pacotes e verifica se há dependências quebradas.
apt-get -f install
Este comando corrige pacotes quebrados quando você recebe reclamações sobre "dependências não atendidas".
Nem ajudou. Como nenhum dos pacotes da Nvidia é necessário no sistema, usei:
apt-get remove <package_name>
Este comando remove um pacote instalado (isso não poderia ser feito no Apper porque o sistema não achava que eles estivessem instalados).
As mensagens sobre problemas ao tentar configurar a Nvidia desapareceram.
Infelizmente, este é apenas um artefato inexplicável de outro problema, um problema com o kernel do Linux. O problema básico com atualizações ainda ocorre, só que agora ele não usa a Nvidia como desculpa. Como isso revelou um problema subjacente diferente, colocarei isso em uma nova pergunta.