lammert - 2:45 am on Apr 29, 2011 (gmt 0)
that serverA has both "authorizedkeys" and "known-hosts" files under ~/.ssh/. The "known-hosts" file has several entries in it, all indicating "ssh-rsa" and the key.
The known-hosts entries are those servers which you have had contact with SSH-ing from serverA to the outside world. You should check if the serverB is listed in the known-hosts file. If that is the case, both servers were able to talk with each other, they only couldn't agree on the authentication type.
Most important are differences in the /etc/ssh/sshd_config files on the two servers. That file configures the SSH daemon which accepts incoming requests.