It is nice to configure sudo with secure PATH. On newer Linux distros (last 2-3 years) you configure sudo with them, so when you invoke a command with sudo, you will know what PATH it searches. I never knew how it worked. For example, if you get:
$ sudo visudo
sudo: visudo: command not found
And this happens with other important binaries. This means you are screwed. This means your PATH is not configured to invoke commands from /usr/sbin , where the 'visudo' binary lies. Add the following to your /etc/sudoers.
Defaults secure_path = /sbin:/bin:/usr/sbin:/usr/bin
You should be good to go now! :)