Ssh public key authentication not working

I had my keys set up so I can ssh between machines without having to enter a password and everything was working for a while but then, all of a sudden, I'm being prompted for a password on some machines.
I verified the keys – everything appears to be OK. I ran ssh -v and here is the output. From what I can tell, the key is being verified successfully, so why am I asked to enter a password???

ssh XXX.XXX.XXX.XXX -v
OpenSSH_4.3p2, OpenSSL 0.9.8e-fips-rhel5 01 Jul 2008
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: Applying options for *
debug1: Connecting to XXX.XXX.XXX.XXX [XXX.XXX.XXX.XXX] port 22.
debug1: Connection established.
debug1: identity file /nethome/username/.ssh/identity type -1
debug1: identity file /nethome/username/.ssh/id_rsa type 1
debug1: identity file /nethome/username/.ssh/id_dsa type 2
debug1: loaded 3 keys
debug1: Remote protocol version 2.0, remote software version OpenSSH_5.3
debug1: match: OpenSSH_5.3 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_4.3
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-ctr hmac-md5 none
debug1: kex: client->server aes128-ctr hmac-md5 none
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<1024<8192) sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY
debug1: Host 'XXX.XXX.XXX.XXX' is known and matches the RSA host key.
debug1: Found key in /nethome/username/.ssh/known_hosts:43
debug1: ssh_rsa_verify: signature correct
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey,gssapi-keyex,gssapi-with-mic,password
debug1: Next authentication method: gssapi-with-mic
debug1: Unspecified GSS failure.  Minor code may provide more information
No credentials cache found

debug1: Unspecified GSS failure.  Minor code may provide more information
No credentials cache found

debug1: Unspecified GSS failure.  Minor code may provide more information
No credentials cache found

debug1: Next authentication method: publickey
debug1: Trying private key: /nethome/username/.ssh/identity
debug1: Offering public key: /nethome/username/.ssh/id_rsa
debug1: Authentications that can continue: publickey,gssapi-keyex,gssapi-with-mic,password
debug1: Offering public key: /nethome/username/.ssh/id_dsa
debug1: Authentications that can continue: publickey,gssapi-keyex,gssapi-with-mic,password
debug1: Next authentication method: password

By the way, I don't see a message that server accepted the authentication:

debug1: Server accepts key: pkalg ssh-rsa blen 277

~/.ssh/ has mode 700, I tried running ssh-copy-id and that seems to have worked.
Just to be sure, I ran md5sum on id_rsa.pub on both machines and they are the same.
Also, the checksum on authorized_keys on the target machine, matches to the checksum of the public key (since it's the only key in authorized keys).