A razão pela qual escrevo esta instrução aqui é que não encontrei uma solução passo-a-passo quando me deparei com o problema. Eu sou um novato em Linux, então sinta-se livre para editar isto:)
Estes passos resolveram o problema para mim:
Inicialize no modo de recuperação (pressione Esc ou saia da Shift após o splash do BIOS)
Selecione a opção Soltar para prompt do shell de root
Monte o sistema de arquivos no modo gravável:
mount -o rw,remount /
Adicione a conexão com a internet (não sei se isso funciona com o Wi-Fi):
dhclient eth0
Agora você tem que limpar o pacote sudo existente. Está protegido contra remoção, então você tem que definir esta variável de ambiente:
export SUDO_FORCE_REMOVE=yes
Limpar o sudo:
apt-get purge sudo
Esse comando também removeu o pacote ubuntu-minimal, portanto, se executarmos
apt-get install ubuntu-minimal
isto irá restaurar ambos os pacotes
Reinicialize o sistema:
reboot