Ssh – passwordless ssh not working

I've tried to setup a password-less ssh b/w A to B and B to A as well.
Generated the public and private key using ssh-keygen -trsa on both the machines.
Used the ssh-copy-id utility to copy the public-keys from A to B as well as B to A.

The passwordless ssh works from A to B but not from B to A.
I've checked the permissions of the ~/ssh/ folder and seems to be normal.

A's .ssh folder permissions:

-rw-------  1 root root 13530 2011-07-26 23:00 known_hosts
-rw-------  1 root root   403 2011-07-27 00:35 id_rsa.pub
-rw-------  1 root root  1675 2011-07-27 00:35 id_rsa
-rw-------  1 root root   799 2011-07-27 00:37 authorized_keys
drwxrwx--- 70 root root  4096 2011-07-27 00:37 ..
drwx------  2 root root  4096 2011-07-27 00:38 .

B's .ssh folder permissions:

-rw------- 1 root root  884 2011-07-07 13:15 known_hosts
-rw-r--r-- 1 root root  396 2011-07-27 00:15 id_rsa.pub
-rw------- 1 root root 1675 2011-07-27 00:15 id_rsa
-rw------- 1 root root 2545 2011-07-27 00:36 authorized_keys
drwxr-xr-x 8 root root 4096 2011-07-06 19:44 ..
drwx------ 2 root root 4096 2011-07-27 00:15 .

A is an ubuntu 10.04 (OpenSSH_5.3p1 Debian-3ubuntu4, OpenSSL 0.9.8k 25 Mar 2009) B is a debian machine (OpenSSH_5.1p1 Debian-5, OpenSSL 0.9.8g 19 Oct 2007)

From A:

#ssh B

works fine.

From B:

#ssh -vvv A 
...
...
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug2: key: /root/.ssh/identity ((nil))
debug2: key: /root/.ssh/id_rsa (0x7f1581f23a50)
debug2: key: /root/.ssh/id_dsa ((nil))
debug3: Wrote 64 bytes for a total of 1127
debug1: Authentications that can continue: publickey,password
debug3: start over, passed a different list publickey,password
debug3: preferred gssapi-keyex,gssapi-with-mic,gssapi,publickey,keyboard-interactive,password
debug3: authmethod_lookup publickey
debug3: remaining preferred: keyboard-interactive,password
debug3: authmethod_is_enabled publickey
debug1: Next authentication method: publickey
debug1: Trying private key: /root/.ssh/identity
debug3: no such identity: /root/.ssh/identity
debug1: Offering public key: /root/.ssh/id_rsa
debug3: send_pubkey_test
debug2: we sent a publickey packet, wait for reply
debug3: Wrote 368 bytes for a total of 1495
debug1: Authentications that can continue: publickey,password
debug1: Trying private key: /root/.ssh/id_dsa
debug3: no such identity: /root/.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
root@192.168.122.1's password: 

Which essentially means it's not authenticating using the file /root/id_rsa.
I ran the ssh-add command in both the machines as well.

the contents /etc/ssh/sshd_config are:

# Package generated configuration file
# See the sshd_config(5) manpage for details

# What ports, IPs and protocols we listen for
Port 22
# Use these options to restrict which interfaces/protocols sshd will bind to
#ListenAddress ::
#ListenAddress 0.0.0.0
Protocol 2
# HostKeys for protocol version 2
HostKey /etc/ssh/ssh_host_rsa_key
HostKey /etc/ssh/ssh_host_dsa_key
#Privilege Separation is turned on for security
UsePrivilegeSeparation yes

# Lifetime and size of ephemeral version 1 server key
KeyRegenerationInterval 3600
ServerKeyBits 768

# Logging
SyslogFacility AUTH
LogLevel INFO

# Authentication:
LoginGraceTime 120
PermitRootLogin yes
StrictModes yes

RSAAuthentication yes
PubkeyAuthentication yes
#AuthorizedKeysFile %h/.ssh/authorized_keys

# Don't read the user's ~/.rhosts and ~/.shosts files
IgnoreRhosts yes
# For this to work you will also need host keys in /etc/ssh_known_hosts
RhostsRSAAuthentication no
# similar for protocol version 2
HostbasedAuthentication no
# Uncomment if you don't trust ~/.ssh/known_hosts for RhostsRSAAuthentication
#IgnoreUserKnownHosts yes

# To enable empty passwords, change to yes (NOT RECOMMENDED)
PermitEmptyPasswords no

# Change to yes to enable challenge-response passwords (beware issues with
# some PAM modules and threads)
ChallengeResponseAuthentication no

# Change to no to disable tunnelled clear text passwords
#PasswordAuthentication yes

# Kerberos options
#KerberosAuthentication no
#KerberosGetAFSToken no
#KerberosOrLocalPasswd yes
#KerberosTicketCleanup yes

# GSSAPI options
#GSSAPIAuthentication no
#GSSAPICleanupCredentials yes

X11Forwarding yes
X11DisplayOffset 10
PrintMotd no
PrintLastLog yes
TCPKeepAlive yes
#UseLogin no

#MaxStartups 10:30:60
#Banner /etc/issue.net

# Allow client to pass locale environment variables
AcceptEnv LANG LC_*

Subsystem sftp /usr/lib/openssh/sftp-server

# Set this to 'yes' to enable PAM authentication, account processing,
# and session processing. If this is enabled, PAM authentication will
# be allowed through the ChallengeResponseAuthentication and
# PasswordAuthentication.  Depending on your PAM configuration,
# PAM authentication via ChallengeResponseAuthentication may bypass
# the setting of "PermitRootLogin without-password".
# If you just want the PAM account and session checks to run without
# PAM authentication, then enable this but set PasswordAuthentication
# and ChallengeResponseAuthentication to 'no'.
UsePAM yes

I'm running out of ideas.
Any help would be appreciated.