Correção simples, se você também não estragar pkexec :
O problema é que o /usr/bin/sudo tem as permissões erradas definidas ( -rwxrwxr-x em vez de -rwsr-xr-x corretas).
Agora, como o arquivo é de propriedade do root, você precisa de permissões de root para alterar suas permissões. Normalmente, você usaria sudo para isso, mas como ele está quebrado, temos que usar pkexec como substituto para repará-lo:
pkexec chmod u+s,g-x /usr/bin/sudo
Agora tudo deve ser corrigido novamente. Experimente o por exemplo comando a seguir para verificar:
sudo echo "sudo works again! Yay! :D"
Correção mais complexa, se você também estragou pkexec :
Primeiro, você precisa inicializar seu sistema Ubuntu no modo de recuperação.
Você faz isso reiniciando e aguardando o menu GRUB aparecer. Isso acontece imediatamente após o BIOS terminar seu trabalho e antes do Ubuntu começar a carregar. Ele normalmente aparecerá se você fizer uma dupla inicialização com outro SO, mas se isso não acontecer, você terá que segurar a tecla Shift para que apareça. Selecione o ponto de menu Advanced options e depois escolha a última versão do kernel com o sufixo (recovery mode) . Você verá outro menu, no qual deverá selecionar root , que mostra um terminal com acesso root.
Mais informações sobre como inserir um shell raiz no modo de recuperação podem ser encontradas here , siga as etapas de 1 a 7 e continue aqui.
Execute os seguintes comandos no shell do root:
mount -o remount,rw /
chmod u=rwxs,g=rx,o=rx /usr/bin/sudo /usr/bin/pkexec
exit
Em seguida, reinicie normalmente e teste seus comandos.