Is there some reason you cannot use DSA? You already know it appears to be checking for that so wouldn't that make it the path of least resistance? If you have to use RSA then have you tried creating an RSA2 key? See below for DSA and RSA2.

Other possiblity is a name/IP address lookup issue -- ssh will do a reverse loookup on the IP address of the client and compare that to the hostname the client claims it is coming from. Keep in mind an entry in /etc/hosts on the client that does not exist in /etc/hosts on the server can further confuse things (Solaris admins should be familiar with this).

And if you have multi-homed systems then routing can also be a factor (i.e. make sure traffic comes in and goes out through the same interface).

ssh-keygen -t dsa
ssh-keygen -t rsa
[download]