RHEL6 manages to break ssh key authentication using ssh-copy-id on the client. Searching the web, I dug out a blog post from John VanDyk where he explains that the problem is related to SELinux. He also provides a solution: Use restorecon to fix the security contexts for the files created by ssh-copy-id. cd /home/me
chmod go-rwx .ssh
restorecon -R -v .ssh
I suspect this only happens if you use ssh-copy-id to create the .ssh/authorized_keys file and place the first key in it.