Public SSH keys not working for all users on same server

I believe you should be inspecting your authorized_keys file on the server. On most systems where I have seen ssh-copy-id it is a very basic script with out a lot of error checking.

On several occasions I have seen it create duplicate entries, or create broken entries in the authorized_keys file. I have seen it upload a different key then what was expected.

For the best results when using ssh-copy-id you should use the -i option to explicitly identify the public portion of the key you want to be uploaded. If you don't the -i option it will pick the first file from a few locations, including from an SSH agent socket.

Take a few seconds to inspect the ssh-copy-id script on your system and you will almost certainly see what I am talking about.

Not really a self standing answer, but not enough rep for a comment on Zoredache's answer.

I would add that on top of checking the permissions and ownership of the file, the directory and the parent directories, check the contents of the file. Depending on how you built the file, it could be that the key is stored as several lines instead of a single line.

I have had this issue copying and pasting keys from one file to another, and because the lines are the same length as the terminal's autowrap, it can be hard to detect.