Hello,
I have five servers Rhel5.5 Tikanga. I have used ssh-keygen several times without problem. My issue here is that servers 2,3,4, and 5 worked flawlessly. Server 1 however, only works outbound passwordless ssh. None of the other servers can ssh into server 1. I have done the following checks comparing server 1 and 2:

Ran the commands
ssh-keygen -t rsa -b 2048
ssh-copy-id ~/.ssh/id_rsa.pub servername
type password
Server 1 to 2 works
Server 2 to 1 fails

All file permissions and ownership are the same from / to ~/.ssh
Ran the command "id" on both servers and entries match
Blew away the keys and regenerated (a few times)
sshd_config files match
ssh_config files match
iptables are off on both machines

Ran ssh -vvvv from one to two (successfully) with the following output:

debug3: check_host_in_hostfile: filename /u01/app/oracle/.ssh/known_hosts
debug3: check_host_in_hostfile: match line 1
debug3: check_host_in_hostfile: filename /u01/app/oracle/.ssh/known_hosts
debug3: check_host_in_hostfile: match line 1
debug1: Host 'server2' is known and matches the RSA host key.
debug1: Found key in /u01/app/oracle/.ssh/known_hosts:1
debug2: bits set: 516/1024
debug1: ssh_rsa_verify: signature correct
debug2: kex_derive_keys
debug2: set_newkeys: mode 1
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug2: set_newkeys: mode 0
debug1: SSH2_MSG_NEWKEYS received
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug2: service_accept: ssh-userauth
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug2: key: /u01/app/oracle/.ssh/identity ((nil))
debug2: key: /u01/app/oracle/.ssh/id_rsa (0x2ac6d1fc1100)
debug2: key: /u01/app/oracle/.ssh/id_dsa ((nil))
debug1: Authentications that can continue: publickey,gssapi-with-mic,password
debug3: start over, passed a different list publickey,gssapi-with-mic,password
debug3: preferred gssapi-with-mic,publickey,keyboard-interactive,password
debug3: authmethod_lookup gssapi-with-mic
debug3: remaining preferred: publickey,keyboard-interactive,password
debug3: authmethod_is_enabled gssapi-with-mic
debug1: Next authentication method: gssapi-with-mic
debug3: Trying to reverse map address "IPADDR".
debug1: Unspecified GSS failure. Minor code may provide more information
Unknown code krb5 195

debug1: Unspecified GSS failure. Minor code may provide more information
Unknown code krb5 195

debug1: Unspecified GSS failure. Minor code may provide more information
Unknown code krb5 195

debug2: we did not send a packet, disable method
debug3: authmethod_lookup publickey
debug3: remaining preferred: keyboard-interactive,password
debug3: authmethod_is_enabled publickey
debug1: Next authentication method: publickey
debug1: Trying private key: /u01/app/oracle/.ssh/identity
debug3: no such identity: /u01/app/oracle/.ssh/identity
debug1: Offering public key: /u01/app/oracle/.ssh/id_rsa
debug3: send_pubkey_test
debug2: we sent a publickey packet, wait for reply
debug1: Server accepts key: pkalg ssh-rsa blen 277
debug2: input_userauth_pk_ok: SHA1 fp 87:b7:09:cf:9c:80:28:8e:3c:0a:f0:53:dd:9f:5e:6a:7f:38:3d:7e
debug3: sign_and_send_pubkey
debug1: read PEM private key done: type RSA
debug1: Authentication succeeded (publickey).

Ran ssh -vvvv from two to one (unsuccessfully) with the following output:

debug3: check_host_in_hostfile: filename /u01/app/oracle/.ssh/known_hosts
debug3: check_host_in_hostfile: match line 1
debug3: check_host_in_hostfile: filename /u01/app/oracle/.ssh/known_hosts
debug3: check_host_in_hostfile: match line 1
debug1: Host 'server1' is known and matches the RSA host key.
debug1: Found key in /u01/app/oracle/.ssh/known_hosts:1
debug2: bits set: 507/1024
debug1: ssh_rsa_verify: signature correct
debug2: kex_derive_keys
debug2: set_newkeys: mode 1
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug2: set_newkeys: mode 0
debug1: SSH2_MSG_NEWKEYS received
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug2: service_accept: ssh-userauth
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug2: key: /u01/app/oracle/.ssh/identity ((nil))
debug2: key: /u01/app/oracle/.ssh/id_rsa (0x2ab65e6d8100)
debug2: key: /u01/app/oracle/.ssh/id_dsa ((nil))
debug1: Authentications that can continue: publickey,gssapi-with-mic,password
debug3: start over, passed a different list publickey,gssapi-with-mic,password
debug3: preferred gssapi-with-mic,publickey,keyboard-interactive,password
debug3: authmethod_lookup gssapi-with-mic
debug3: remaining preferred: publickey,keyboard-interactive,password
debug3: authmethod_is_enabled gssapi-with-mic
debug1: Next authentication method: gssapi-with-mic
debug3: Trying to reverse map address "IPADDR".
debug1: Unspecified GSS failure. Minor code may provide more information
Unknown code krb5 195

debug1: Unspecified GSS failure. Minor code may provide more information
Unknown code krb5 195

debug1: Unspecified GSS failure. Minor code may provide more information
Unknown code krb5 195

debug2: we did not send a packet, disable method
debug3: authmethod_lookup publickey
debug3: remaining preferred: keyboard-interactive,password
debug3: authmethod_is_enabled publickey
debug1: Next authentication method: publickey
debug1: Trying private key: /u01/app/oracle/.ssh/identity
debug3: no such identity: /u01/app/oracle/.ssh/identity
debug1: Offering public key: /u01/app/oracle/.ssh/id_rsa
debug3: send_pubkey_test
debug2: we sent a publickey packet, wait for reply
debug1: Authentications that can continue: publickey,gssapi-with-mic,password
debug1: Trying private key: /u01/app/oracle/.ssh/id_dsa
debug3: no such identity: /u01/app/oracle/.ssh/id_dsa
debug2: we did not send a packet, disable method
debug3: authmethod_lookup password
debug3: remaining preferred: ,password
debug3: authmethod_is_enabled password
debug1: Next authentication method: password

What have I missed?

You need to run "ssh key-gen" on server 2 and create an id_rsa.pub file on there. Then take the contents of that file and add/append it to the authorized_keys file on server 1.

So, let's say server 2 has this
# cat /home/user/.ssh/id_rsa.pub
123456789

on server 1, you need to have this
# cat /home/user/.ssh/authorized_keys
123456789

That should do it

I did that process both ways. I have an authorized_keys file on both machines now that contains each others id_rsa.pub.

Let's triple check permissions. Please post output from:
(run on both hosts)

Face Palm...........Thank you Anomie. I think I had looked at this too long. I looked this morning, ran the ls -ld and immediately found my problem. Server1 was 775 on /u01/app/oracle and Server2 was 750. Made them both 750 and now they are happy. I swear I checked perms a dozen times. Guess I needed a break and some good advice.