sudo seems to be fussy. Try using the whole path as you have written it in /etc/sudoers when calling shutdown.

Code:
sudo /sbin/shutdown -k