Q:

Public SSH keys not working for all users on same server

I have a VPS on which I have multiple "users" (all me, for different things). I configured my local SSH public keys and used ssh-copy-id to copy to all of them. I am able to login without a password prompt only for some of them, however, and it's driving me crazy.
I used ssh -v user@host.ip.address for one that works, and one that doesnt. The output text is all EXACTLY the same until toawrd the end:
The one that works looks like this: 
debug1: Next authentication method: publickey
debug1: Offering RSA public key: /home/tom/.ssh/id_rsa
debug1: Server accepts key: pkalg ssh-rsa blen 279
debug1: Authentication succeeded (publickey).
Authenticated to xxx.xxx.xxx.xxx ([xxx.xxx.xxx.xxx]:22).
debug1: channel 0: new [client-session]
debug1: Entering interactive session.
debug1: Sending environment.
debug1: Sending env LANG = en_US.UTF-8

The one that doesn't looks like this: 
debug1: Next authentication method: publickey
debug1: Offering RSA public key: /home/tom/.ssh/id_rsa
debug1: Authentications that can continue: publickey,password,keyboard-interactive
debug1: Trying private key: /home/tom/.ssh/id_dsa
debug1: Trying private key: /home/tom/.ssh/id_ecdsa
debug1: Next authentication method: keyboard-interactive
debug1: Authentications that can continue: publickey,password,keyboard-interactive
debug1: Next authentication method: password

I have double checked that the key and file permissions in authorized_keys is the same for each user and the .ssh folder, but for some reason the server isn't accepting the same exact key, which IS the same exact key stored on the server. 
I have tried restarting the sshd daemon as well as the server.

A:

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.

