GitLab: Failed to authorize your Git request: internal API unreachable

I installed a gitlab Server for internal use of my company doing

sudo apt-get install curl openssh-server ca-certificates postfix
curl -sS https://packages.gitlab.com/install/repositories/gitlab/gitlab-ce/script.deb.sh | sudo bash
sudo apt-get install gitlab-ce
sudo gitlab-ctl reconfigure

I activated Git-LFS in the gitlab.rb and I added the omniauth_providers Github App

I managed to import all repos and they seem intact. Everything workes fine and we can PULL all our repos including large files and they run as expected.

BUT:

We can't push/commit not on the webinterface nor remote.

It alsways hangs at POST git-receive-pack (809 bytes) for a while and than exits with remote: GitLab: Failed to authorize your Git request: internal API unreachable

This is how my /etc/gitlab/gitlab.rb looks like

external_url 'http://holo-git/'

 gitlab_rails['gitlab_email_enabled'] = true
 gitlab_rails['gitlab_email_from'] = 'info@holo-git'
 gitlab_rails['gitlab_email_display_name'] = 'Git-Server'
 gitlab_rails['gitlab_email_reply_to'] = 'noreply@holo-git'
 gitlab_rails['gitlab_email_subject_suffix'] = "[GIT]"

 gitlab_rails['gitlab_default_can_create_group'] = true
 gitlab_rails['gitlab_username_changing_enabled'] = true

 gitlab_rails['gitlab_default_projects_features_merge_requests'] = true

 gitlab_rails['lfs_enabled'] = true
 gitlab_rails['lfs_storage_path'] = "/mnt/storage/lfs-objects"

 gitlab_rails['omniauth_enabled'] = true
 gitlab_rails['omniauth_providers'] = [
   {
     "name" => "github",
     "app_id" => "XXXXXXXXXXXXXXXXXX",
     "app_secret" => "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
     "url" => "https://github.com/",
     "args" => { "scope" => "user:email" }
   }
 ]

I've also read something about uncommenting gitlab_rails['unicorn_workers]=2 but this didn't solve anything.

EDIT: PUSH works if there where no changes at all:

Pushing to http://username@holo-git/Team/repo.git
Branch master set up to track remote branch master from origin.
To http://holo-git/Team/repo.git
 = [up to date]      master -> master
updating local tracking ref 'refs/remotes/origin/master'
Everything up-to-date