Can you run any other programs with 'sudo ' (eg gedit)?
If no, can you run them from the terminal without the 'sudo ' bit?
If yes, can you check in Synaptic to see if sudo is installed?
If it is, try re-installing it (and take the obvious action if it isn't