sudo must be owned by uid 0 and have the setuid bit set
Solution 1:
The Setuid bit is not set. If it were, the permissions would have an s instead of the first x:
$ ls -l /usr/bin/sudo
-rwsr-xr-x 1 root root 155008 Feb 11 2014 /usr/bin/sudo
Try using pkexec to set it correctly:
pkexec chmod a=rx,u+ws /usr/bin/sudo
Though I doubt that's the only problem you are going to have.
Solution 2:
Login with root (su) and run the following command
chown root:root /usr/bin/sudo && chmod 4755 /usr/bin/sudo