A note for my future self.
Summary: When adding a new production server to my cap deploy that will clone a repository from my gitolite server, First SSH into the gitolite server so the production server has the gitolite server in it's trusted hosts file.
A repository on my gitolite server wouldn't allow a new server to read it. Cap Deploy failed with lines like:
failed: "sh -c 'git clone -q firstname.lastname@example.org:myrepo.git ....
I couldn't find any logs on the gitolite server to help. Whilst fault finding I read that gitolite replied to a standard SSH login with details about Repo's you can access.
When I tried, I got the ssh untrusted host warning. Having added the host to my trusted hosts, my cap deploy worked fine.