I have a Solaris 10 client connecting to a RHEL 6.x server. I have the below configured in my sshd_config, but my client continues to get prompted for a password:

Protocol 2
HostKey /etc/ssh/ssh_host_rsa_key
HostKey /etc/ssh/ssh_host_dsa_key
PermitRootLogin no
StrictModes no
RSAAuthentication yes
PubkeyAuthentication yes
AuthorizedKeysFile /home/%u/.ssh/authorized_keys
/etc/ssh/ssh_known_hosts
RhostsRSAAuthentication no
HostbasedAuthentication no
IgnoreRhosts yes
PermitEmptyPasswords no
PasswordAuthentication yes
ChallengeResponseAuthentication no
GSSAPIAuthentication no
GSSAPICleanupCredentials no
UsePAM yes
Ciphers aes128-ctr,aes192-ctr,aes256-ctr
MACs hmac-sha1

Despite having PubkeyAuthentication yes I'm seeing:
Authentications that can continue: password

Instead of:
Authentications that can continue: publickey,password

The perms on the user home directory and .ssh are 700, and the authorized_keys is 600. All are also owned by the user.

I was also able to use the client's private key on the server to connect from my server into itself and was able to authenticate without being prompted for a password.

Any suggestions will be greatly appreciated.

Can you check the ssh_config on the Solaris machine?
Are you sure that you have properly moved and placed the pub key from the Solaris box onto the RH box?
Have you tried ssh with -vvv on the client side, and check the connection trace from ssh on the RH side?

I have. So far I've done the following:

1. On Linux1(server side), used the Solaris1(Client side) private key and successfully connected back to the Linux1 server.
***Linux1 to Linux1

2. On Linux1(server side), used the Solaris(Client side) private key and successfully connected to another Linux2 server.
***Linux1 to Linux2

3. From Solaris1(client) connected to another Solaris2 machine.
***Solaris1 to Solaris2

4. From Solaris1(client) connected to another Linux3 machine.
***Solaris1 to Linux3

I just can't get Solaris1 to connect to Linux1.

It turns out that the firewall on the Solaris client side was configured to do protocol filtering,
but once changed to packet filtering everything worked!

So, protocol filtering allowed the connection, but disabled key authentication?
Not the behavior I would have expected. Thank you for sharing that! I will add that to my list of things to watch out for.

Imagine our firewall guy's reaction! He was 100% sure the firewall had no impact on this. I had to send him an error message that referenced the firewall after I disabled PasswordAuthentication.

To be certain we had him change the setting back to protocol filtering and it prompted for a password again.