Comment 27 for bug 434799

Andrew, in my experience the problem is that restarting a service (i.e. "service ssh restart") does not apply configuration changes.

So please try like this:

initctl reload-configuration
sevice ssh stop
service ssh start

It worked for me (while restart did not work).