I'm having a similar problem. I checked through the forum here and Google, and the only advice I found was to make sure the command I'm trying to run is SUID root, and that it's not on a partition mounted with the nosuid option.
I'm running on a VPS if that helps (/etc/fstab doesn't show me anything, but I don't think it would be mounted with a nosuid option (?)
I'm trying to enable sudo to the '/sbin/service' command.
The sudo command is SUID root, I even did chmod 4111 earlier to be sure:
---s--x--x 1 root root 93816 Apr 29 20:47 /usr/bin/sudo*
But when I try to run a sudo command to stop/stop a service, I get the error:
Sorry, sudo must be setuid root.