Why strace sudo command bombs when sudo command works?
The "must be setuid root" is caused by running sudo in strace.
From man strace:
BUGS Programs that use the setuid bit do not have effective user ID privileges while being traced.
If you want to strace setuid things and have the setuid bit honored, you have to run strace as root with the -u option (this question has already been submitted : Strange strace and setuid behaviour: permission denied under strace, but not running normally)