I just got done setting up a user in my new developer environment on multiple boxes. I made sure to copy over the authorized_keys file exactly, including the correct 0600 permissions, but kept getting the "Permission denied (publickey)" error when trying to ssh into one box, even though all the others worked.
What finally solved it for me was to make sure the user's password is set:
# passwd <user>
If that doesn't work, make sure the user's .ssh directory is chmod 0700 and the user's authorized_keys file is chmod 0600.