sudo: must be setuid root

This error means: permissions of the sudoers file has been changed.

Solution:

Boot into Recovery Mode and enter a shell prompt. Then run these two commands.

    chown root:root /usr/bin/sudo  chmod 4755 /usr/bin/sudo

To boot in recovery mode :
Hold the shift key down as soon as you poweron the computer. Silly grub2 hides menu by default unless it detects multiple OS.

Check permissions on this:

Code:

ls -la /etc/sudoers  -r--r----- 1 root root 828 2010-08-03 11:19 /etc/sudoers

To modify if permissions are wrong:

Code:

chown root:root /etc/sudoers

Code:

chmod 440 /etc/sudoers

Source: http://ubuntuforums.org/showthread.php?t=1548164