esta resposta aqui não é a mais aceita, mas é a perfeita!
diz:
Efetue logout como o usuário atual e faça login novamente como root.
Executar chown root:root /usr/bin/sudo && chmod 4755 /usr/bin/sudo
Efetue logout como root e efetue login novamente como usuário atual.
se você não consegue acessar o usuário root, então você precisará de um live cd ou qualquer sistema operacional Linux instalado em algum lugar e usar o chroot!
atualização:
faça login como root e tente os seguintes cmds:
mount -o remount,rw /
mount --all
chown root:root /usr/bin/sudo
chmod 4755 /usr/bin/sudo
restart