I bought a TonidoPlug, which is a wall-wart with an embedded Linux server (running Ubuntu 9.04 Jaunty). Out of the box, sudo gave the error:
sudo: must be setuid root
This message means exactly what it says -- the sudo command is not setuid and it must be setuid (and owned by root).
chown root:root /usr/bin/sudo chmod u+s /usr/bin/sudo
will correct the 'problem.' (I put quotes around 'problem' because there are some who will say that this is a security feature.)