I've had this one as a draft post for a while and I just ran into the it again, so it's time to to publish it.
I had a Linux server setup that I was getting a new developer to connect to. Whatever we tried, we could not get him logged in via ssh using keys. I verified the home directory permissions (at most 755), the .ssh directory permissions (700), the permissions of the files in the .ssh directory (600). Other users could connect to the server using keys. The developer could use the same client to connect to other ssh servers using keys.
Finally it occurred to me to check the SELinux context on the .ssh directory; it was missing the ssh_home_t context. The repair is simple: restorecon -r -vv .ssh
If you don't trust restorecon or you are just looking for an alternate fix, you can delete the .ssh directory and have the user connect to another ssh server from the target machine. This will build the .ssh directory on the target server when the known_hosts file is created.
