I was also struggling along for some time and I had to change another line in /etc/sshd_config:

"StrictModes yes" to "StrictModes no"

Maybe this is because I used the private and public key from another host (?)