SSH Key-based authentication fails
Solution 1:
I've seen this happen when the user's home directory isn't local, but on an NFS automount on the network. If your home directory isn't already mounted when sshd goes to look for your ~/.ssh/authorized_keys, it won't be able to access it in time, so public-key-based authentication will fail.
Solution 2:
Can't comment so...
If you stop the sshd service (service sshd stop) on your server you can run it interactively to get some debug output (sudo sshd -D). It may be related to the file protections on ~/.ssh and ~/.ssh/authorized_keys.