Keep an eye out for this one. When using ssh-copy-id to copy my public key to a remote host, I found that it had not properly appended my id to the remote ~/.ssh/authorized_keys file. It concatenated it on to the end, with no linefeed. Just be sure to check for that!
Original remote ~/.ssh/authorized_keys
ssh-dss AAA...== forest@machine
After ssh-copy-id did its work:
ssh-dss AAA...== forest@machinessh-dss AAAAB...gdA== forest@laptop