OK I put it in the subject hoping people will NOT bombard me with the usual responses about permissions on the user's home directory or the user's .ssh subdirectory NOR about options in sshd_config. There are thousands of posts on the internet that make those suggestions and none of them are the case here.

So the issue is this:
We are trying to do an sftp connection to a remote site (which I don't have control of so can't see logs on). From one RHEL5.9 server to that remote site I was able to send the contents of id_rsa.pub and have them create a trust to one user. That is working fine.

We then tried to do same from another user on a different RHEL5.9 server. That fails to work and gives error:
Permission denied (publickey).
Couldn't read packet: Connection reset by peer

After much testing I've found that:
1) It gives above error from ANY account that contains id_rsa* and/or id_dsa* files.
2) It prompts for password from any account that does NOT contain the id_* files.
3) If I specify "sftp -o PubkeyAuthentication=no <user>@<remote_site>" I do not get the publickey error and it prompts for password even if I have the id_* files. (Presumably because tht is telling it to ignore keys.)

Using only rsa in the directory does not help.
Using only dsa in the directory does not help.
Reducing the key size from 2048 to 1024 does not help.
Recreating the keys from scratch with ssh-keygen does not help.

It seems clear the issue is that there is a problem with it accepting keys from my side but these same keys work to various other locations and it is only to this remote I have the issue. My expectation would be that if I didn't give it the right key for the trust rather than just failing it would prompt me for password but it doesn't.

I would think the issue was wholly the remote if I hadn't already gotten the first account to work there using rsa key for the trust.

I would think issue might be a difference in the local systems here but they both run the same version of RHEL and have the same version of ssh-keygen, same sshd_config etc...

As noted above I've ruled out permissions issues on the locals. Also if it were permissions it shouldn't work even with password.

If the issue were permissions on the remote then it shouldn't work even with password but does as noted above.

As I understand it the remote is an appliance (Windows based?). The output mentions CoreFTP-0.3.2 which I'm assuming is the software that is actually doing the communication from that appliance. I'm hoping someone has seen this specific issue before.

As noted I've read many, many posts but they all essentially say to check the permissions and the sshd_config but these aren't the issue as they've been checked and rechecked.

verbose output (sanitized to protect the guilty) of the sftp that fails is:

sftp -v <user>@<remotesite>

Sorry but how do you know it's not sshd config issue ?
I recall solving a key problem by changing the AuthorizedKeysFile in sshd_config
(set it to check .ssh/authorized_keys2 instead of .ssh/authorized_keys)

Usually, public keys are saved in the .ssh hidden-directory of a particular destination, e.g. the home directory of the user to whom you are connecting. And there are very specific requirements as to the permissions of both this directory and of the files therein. If you're getting "pubkey," it basically means that the list of acceptable keys in the target that you're trying to contact doesn't include the key that the sender has offered. ("None of the keys fit this lock.")

There is already lots of information about SSH out there ... please Google it carefully. (There are also "stickies.") Then, having done so, ask here about particular questions. This will be, by far, the fastest way to get past your roadblocks so that you can be on your way with this.

As expected I didn't get any helpful responses. I DID explain I had looked at this until I was blue in the face and DID work on ruling out the two main responses nearly every post on the internet suggest.

The way I know it isn't the sshd_config is because:
a) The sshd_config on the server on which it worked for the trust and the one it didn't are the same.
b) The test accounts for which it did not work are on the same server as those for which it did prompt for password (meaning they're using EXACTLY the same setup OTHER than the key files in $HOME/.ssh).

As it turns out the issue with the test server trust turned out to be that the folks running the appliance had misapplied the RSA key I'd sent them. Once they re-applied it the trust began working WITHOUT CHANGING ANYTHING ON MY SERVER.

The way I know it isn't permissions is because:
a) It prompted for password from some accounts but not for others and all had the same permissions all the way up to root from $HOME/.ssh.
b) After the the key was reapplied the trust worked with no permissions change on my end required.

I'm marking this as resolved. It appears to me from all my testing that the issue is that the CoreFTP application (or the appliance that it is running from):
1) Allows for password logins via sftp.
2) Allows for a single trusted key to be setup.
3) Rejects ANY key other than the trusted key and FAILS the connection rather than prompting for a password once a trust has been configured. (That is if you have an id_dsa.pub and/or id_rsa.pub it fails - otherwise it prompts for password.)
4) Will still allow a password login even if you DO have id_dsa.pub or id_ras.pun as one passes the the "-o PubkeyAuthentication=no" flag. (i.e. It never attempts the keys so never rejects them and fails.)

Of course some will say I could add that to the sshd_config file but I've never had to do that for any other connection. Usually if the remote doesn't like the keys it rejects them THEN prompts for the password. This is the first remote I've run into that fails it without prompting for password. I don't plan to make a global change to sshd_config for this kind of thing.