Para o Xenial Xerus:
andrew@athens:~$ apt-cache search gitolite
gitolite3 - SSH-based gatekeeper for git repositories (version 3)
git-notifier - git commit email notification script
andrew@athens:~$
Então seu comando deve ser:
sudo apt-get install git gitolite3
Isso mudou de versões anteriores do Ubuntu ...