Resolving gitolite's "remote: FATAL: fingerprinting failed for 'keydir/some_user.pub'"
Digging about in the gitolite code reveals this error is thrown when a regex fails to find a valid looking fingerprint after running ssh-keygen -l -f 'path/to/key.pub'. (See man ssh-keygen for details).
To resolve the issue, run that command locally and have it generate a valid fingerprint before you push your configuration changes to the gitolite server. I found my issue was that I had failed to include the 'ssh-rsa ' prefix to the key.
I also saw comments suggesting this issue was related to key size. I saw successful tests using the '-b 1024' and the '-b 2048' switches, so I have serious doubts that the key-size theory holds water. It does not seem supported by a code review of the complaining function.
I seem to encounter this error every few months. It looks familiar to me. Hopefully this blog post might get indexed by the search engines and I will be saved the lost time researching this question yet again, or if noy me, then perhaps others.