openssh-5.1 problem?

[YONETANI Tomokazu]

Hello.
After openssh has been updated to openssh-5.1p1, slogin'ing to that host
from another machine using DSA key stopped working:
  WARNING: DSA key found for host vmware
  in /home/yonetani/.ssh/known_hosts:3
  DSA key fingerprint 0a:73:33:d7:73:ff:e9:4f:60:e4:de:e1:5b:ec:b6:4d.
  [strange AA omitted]

  The authenticity of host 'vmware (172.16.203.128)' can't be established
  but keys of different type are already known for this host.
  RSA key fingerprint is 02:88:d3:b5:52:3e:a8:3f:4a:fd:3d:fa:99:81:ca:0b.

I can't slogin into that machine unless I accept the RSA key.  So I
investigated a bit and found the following things:

A) running ssh-keyscan against the machine when it's running the previous
  version of sshd gives `no hostkey alg' message whereas it gives the
  correct RSA key when it's running the new version of sshd.

B) If I move away the host_rsa_key* from under /etc/ssh on the machine
   running newer sshd, I can connect to that machine without the warning
   shown above.

C) same thing happens when I try to connect to itself on the machine with
   newer ssh and sshd installed.  however, if I copied the ssh command
   over from 2.0-RELEASE machine and use it to connect to itself (but
   with newer libcrypto and libssh), it doesn't complain about the DSA key.
   note I moved host_rsa_key* files back into the place before doing this.

D) The version information reported by `ssh -V' has nothing to do with the
   ssh command itself, but something else (libssh or /etc/ssh/ssh_config?)

"A" implies that the newer openssh-5.1 fixed the problem in sshd that it
couldn't return RSA key.
"B" together with "C" imply that apparently this is a problem (a bug?)
in ssh command itself, not the shared libraries it's linked against, that
it fails to verify the DSA host key if the server also replies with an RSA
host key.

Any ideas?