Dealing with "[HOST_KEY_NOT_VERIFIABLE] Could not verify `ssh-rsa` host key with fingerprint" in sshj

I having a strange issue with sshj (am using sshj v0.6.0) for which I would need some help from someone. Authentication with public key works fine on some machines but doesnt work fine on other machines and I see the below error.

The only difference that I could make out was that the UNIX ID in question viz coonradt seems to have the below listed configuration setup under ~/.ssh/config only on the box on which the below errors are being triggered

Host *
    Protocol 1,2
    FallBackToRsh no
    ForwardAgent yes
    ForwardX11 yes
    PasswordAuthentication yes
    RhostsAuthentication no
    RhostsRSAAuthentication no
    RSAAuthentication yes
    NoHostAuthenticationForLocalhost yes
    StrictHostKeyChecking no
  KeepAlive yes

From the above config file I learnt that the ID in question is supposed to make use of Protocol 1,2 and I suspect that this might have something to do with my failures (I am not very sure about it, but this is just a hunch)

For all other UNIX IDs for which this works fine, I dont have any such config file.

PS : I cannot alter the config of the UNIX ID "coonradt" since this ID is being used by the central hudson servers.

Would appreciate if someone could please help me suggest as to what might be wrong here

Following is the error that I am seeing :

Oct 24, 2011 2:30:37 AM net.schmizz.sshj.DefaultConfig initCipherFactories
WARNING: Disabling high-strength ciphers: cipher strengths apparently limited by JCE policy
Oct 24, 2011 2:30:38 AM net.schmizz.sshj.transport.TransportImpl init
INFO: Client identity string: SSH-2.0-SSHJ_0_6_0
Oct 24, 2011 2:30:38 AM net.schmizz.sshj.transport.TransportImpl init
INFO: Server identity string: SSH-1.99-OpenSSH_4.3
Oct 24, 2011 2:30:38 AM net.schmizz.sshj.transport.KeyExchanger sendKexInit
INFO: Sending SSH_MSG_KEXINIT
Oct 24, 2011 2:30:38 AM net.schmizz.sshj.transport.KeyExchanger handle
INFO: Received SSH_MSG_KEXINIT