Sorry, sudo must be setuid root.
I got this error a couple of times, usually because I ran a recursive chmod command on a directory which had sudo symlinked inside.
After this sudo or other affected commands which must be setuid root won't run.
The solution: Find the affected command by which sudo or which... where ... is the affected command.
Then:
| # chown root:root /usr/bin/sudo # chmod 4111 /usr/bin/sudo |