I just hit this problem while working on a new install. There was a change to the key fingerprint format in OpenSSH at version 6.8:
Add FingerprintHash option to ssh(1) and sshd(8), and equivalent
command-line flags to the other tools to control algorithm used
for key fingerprints. The default changes from MD5 to SHA256 and
format from hex to base64.
Fingerprints now have the hash algorithm prepended. An example of
the new format: SHA256:mVPwvezndPv/ARoIadVY98vAC0g+P/5633yTC4d/wXE
Please note that visual host keys will also be different.
The latest git checkout of gitolite is aware, since 18th March '15, of this new format.