I had this weird problem with some deployments on dev boxes that was proving difficult to resolve. With a public/private keypair set up, correct permissions on the keys and the authorized_yes file, I kept getting denied on a key based login:
$ ssh somehost .... debug1: Offering RSA public key: /home/user/.ssh/id_some_key debug3: send_pubkey_test debug2: we sent a publickey packet, wait for reply debug1: Authentications that can continue: publickey debug2: we did not send a packet, disable method debug1: No more authentication methods to try. Permission denied (publickey).
Signing in on a rescue console as the user worked. After that, signing in via SSH worked without error.
As it turns out, having an encrypted home directory causes the authorized_keys file on the box to be unreadable by SSH. Signing in on the rescue console decrypts the home, allowing subsequent SSH logins to work -- which makes complete sense. The workaround is to update this setting in /etc/ssh/sshd_config on the actual box (manually or in your Ansible / Puppet / etc plays)
Move the user's ~/.ssh/authorized_keys file to /etc/ssh/home/user/ (%h is expanded to /home/user). Ensure that "user" has ownership of the /etc/ssh/home/user directory and that it and the authorized_keys file have the correct permissions (0700 and 0600 respectively).
Of course, your authorized_keys files will no longer be encrypted.
Once that's done restart SSH and you'll be able to sign in to to your box with an encrypted home.