What could cause an SFTP host key fingerprint mismatch?

A remote user has tried to connect to my SFTP/SSH server for the first time, using the "Transmit" client under Mac OS X, and has found that the host key fingerprint doesn't match the expected value.

I have a screenshot of the displayed fingerprint and have compared it with the output of ssh-keygen -lf /etc/ssh/ssh_host_dsa_key and ssh-keygen -lf /etc/ssh/ssh_host_rsa_key.pub, and it doesn't match either of these.

I have also unsuccessfully compared the fingerprint against the output of cut -d ' ' -f 2 < /etc/ssh/ssh_host_dsa_key.pub | base64 -d | sha1sum and cut -d ' ' -f 2 < /etc/ssh/ssh_host_rsa_key.pub | base64 -d | sha1sum (because it seems that there are different fingerprinting algorithms in use?).

The message box on client side is titled (translated into English)

Unknown host key for < hostname >

and states

The server is unknown. The fingerprint of the host key is < 16 octets >. ( Allow ) ( Deny ) [ ] Always

So there is no indication whether RSA or DSA key is used, or whether MD5 or some SHA algorithm is used for creating the fingerprint.

The fingerprint displayed to the remote user has 16 colon-separated octets, so it doesn't appear to use SHA-224 or anything higher. Update: I just noticed that even an SHA-1 hash will have 20 octets, so the displayed fingerprint is not in any SHA format apparently.

The connection ultimately goes to the correct server, because I can see the login attempt in my server logs if the user allows the connection. So it appears that the host name/IP is entered correctly on client side.

A connection to another (completely unrelated) SFTP server shows an incorrect fingerprint as well (but a different one than for the first server).

If I try to connect to the server myself using OpenSSH from some other host (or locally from the server itself), I am shown the correct fingerprint (the MD5 fingerprint for RSA host key).

The server is running Debian 6 LTS with the standard OpenSSH server.

What could cause this fingerprint mismatch? How can I debug this problem?

If it is the first time they connected, it doesn't matter if there's a mismatch... the client just had some unrelated old entry that happened to have the same host name or ip address associated with it. Just clear it with:

ssh-keygen -R $name_or_ip

After you do that, it should certainly say whether it is RSA, ECDSA, etc. the next time you connect. If not, try using a proper client like the OpenBSD OpenSSH client which is standard on Linux, or trying -v (or -vvvv, etc. verbose options). And then verify and accept the new key. The key fingerprint format in old clients is md5 (and in new ones is sha256, in some weird base64 format instead of ascii-hex), and the right way to get the fingerprint on the server side is:

ssh-keygen -l -f /etc/ssh/ssh_host_rsa_key

Turns out that the FTP program in use was not Transmit but was Cyberduck 4.5.1. The problem with the wrong fingerprint was already known as Wrong host key fingerprint. Updating to the latest version fixed this problem, and the displayed fingerprint is now correct.