In Ubuntu, install sshd client and server with these commands:
sudo apt-get install openssh-client
and
sudo apt-get install openssh-server
Then, to restart sshd, type:
sudo /etc/init.d/ssh restart
This worked for me, when I had the same problem. You can find more information here.