bash: /usr/bin/ssh: Permission denied

This message has been a headache, happening a couple of times when I upgrade or update packages.

albertsk@stokes:~$ ssh
bash: /usr/bin/ssh: Permission denied


root@stokes:ssh$ ll /usr/bin/wget
-rwxr-xr-x 1 root root 369848 Feb 10  2012 /usr/bin/wget*

root@stokes:ssh$ chmod og+x /usr/bin/ssh
chmod: changing permissions of `/usr/bin/ssh': Operation not permitted

root@stokes:ssh$ ll /usr/bin/ssh
-rwx------ 1 root root 650492 Feb 12 01:46 /usr/bin/ssh*

root@stokes:ssh$ chmod og+x /usr/bin/ssh
chmod: changing permissions of `/usr/bin/ssh': Operation not permitted

root@stokes:ssh$ lsattr /usr/bin/ssh
-u---a-------e- /usr/bin/ssh

root@stokes:ssh$ lsattr /usr/bin/wget
-------------e- /usr/bin/wget

root@stokes:ssh$ chattr -uai  /usr/bin/ssh

root@stokes:ssh$ lsattr /usr/bin/ssh
-------------e- /usr/bin/ssh

root@stokes:ssh$ chmod og+xr  /usr/bin/ssh
root@stokes:ssh$ ls /usr/bin/ssh
/usr/bin/ssh

albertsk@stokes:~$ ssh localhost

Last login: Tue Feb 19 15:10:25 2013 from localhost

Welcome to Ubuntu 12.04.2 LTS (GNU/Linux 3.2.0-37-generic x86_64)

 * Documentation:  https://help.ubuntu.com/

albertsk@stokes:~$