Unless you installed it, it won't be on your system. The reason you are getting the error is, I believe, the following:
You are connecting with a particular key that is recognized in the file of
~git/.ssh/authorized_keys. In there you might have found an entry like this:
# gitolite start
ssh-rsa AAAAB3N.....<snip>... YOURNAME@whereever.the.ssh.key.came.from.com
# gitolite end
So instead of honouring your settings of the default shell that you set using
chsh, the sshd interferes and starts a particular program (in this case gitolite-shell). It is part of the cunning gitolite setup and desired behaviour. In your setup you were missing gitolite or maybe just the appropriate link in ~git/bin to it. Unfortunately, you won't be able to verify this now.
If you do want to try it, you might choose to install from the up-to-date repository (instructions here) since the ubuntu version 2.2 is behind the official v.3.4.