Consegui corrigir o script. Como o sidekiq: start deamoniza a si mesmo, eu precisava colocá-lo em um ambiente de pós-início e pós-parada.
# /etc/init/gitlab-sidekiq.conf - Sidekiq config for gitlab
# use the service command:
# sudo service gitlab-sidekiq {start,stop,restart,status}
description "Sidekiq Background Worker for Gitlab"
start on runlevel [2345]
stop on runlevel [!2345]
# change to match your deployment user
setuid git
setgid git
env HOME=/home/git
env PATH="/usr/local/rvm/gems/ruby-1.9.3-p429@gitlab/bin:/usr/local/rvm/gems/ruby-1.9.3-p429/bin:/usr/local/rvm/gems/ruby-1.9.3-p429@global/bin:/usr/local/rvm/rubies/ruby-1.9.3-p429/bin:/usr/local/rvm/bin:/usr/bin:/bin"
env GEM_PATH="/usr/local/rvm/gems/ruby-1.9.3-p429@gitlab:/usr/local/rvm/gems/ruby-1.9.3-p429@global"
env RAILS_ENV="production"
post-start script
cd /home/git/gitlab
exec bundle exec rake sidekiq:start
end script
post-stop script
cd /home/git/gitlab
exec bundle exec rake sidekiq:stop
end script