No me arrancaba el servidor sshd de ninguna manera con ubuntu 14.04. La única manera de arrancarlo es con lo que dice Pavel Kostenko en su respuesta aquí:
http://askubuntu.com/questions/53463/ssh-problem-after-update
Pasos resumidos:
start-stop-daemon --start --pidfile /var/run/sshd.pid --exec /usr/sbin/sshd -- -p 22
Si sale este error:
Missing privilege separation directory: /var/run/sshd
Crreamos el directorio, modificamos los permisos e intentamos arrancarlo de nuevo:
sudo mkdir /var/run/sshd
sudo chmod 0755 /var/run/sshd