If the permissions on the sudo binary are correct (the 4th character in the "ls -l" output must be 's' and the owner must be root) then it is possible that the underlying file system is mounted with the nosuid flag (or exported in the case of an NFS file system). - todd