[Hampshire] ssh permission denied?

Hi,

I'm not sure when this happened but I've just tried to ssh out from a
machine and got the following:

$ ssh
-bash: /usr/bin/ssh: Permission denied

a quick check reveals:

$ ls -ltr /usr/bin/ssh
-rwx------ 1 root root 650556 Jan 10 13:54 /usr/bin/ssh

so I tried this:

# chmod 755 /usr/bin/ssh
chmod: changing permissions of `/usr/bin/ssh': Operation not permitted

This is on a VPS running Debian lenny which I've certainly managed to ssh
out of before but I probably haven't tried to ssh out of the machines for
a week or two so I'm not sure when the problem started. However I did an
upgate/upgrade yesterday.

Any ideas what is going on?

Andy