This is one of the weirder issues and I am still not entirely sure, how that happens.
My current guess is, that it has something to do with the git repository in question being private and hosting mulitple gems.
To fix this, there is one really simple step:
$ bundle install --path vendor/cache
afterwards, a normal
bundle install will work again.