I agree with mfillpot, and you could verify if that is the issue by specifying the absolute path to the binary as root. If it works, then thats what the issue is.
I'll bet a beer that's the problem :)
Logged in as root and after "su". You'll see the difference.
Check /etc/profile and /etc/login.defs as well as /etc/bashrc or whatever files you might source on your login process.