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.)