Parece que o seu executável sudo tem as permissões erradas. Experimente ls -l /usr/bin/sudo e veja o que ele diz. Ele deve se parecer com -rwsr-xr-x (ou ---s--x--x ; no entanto, o s precisa estar nessa posição). Se o s não estiver lá, tente executar chmod u+s /usr/bin/sudo como root.