Esta é uma das questões mais estranhas e ainda não tenho certeza de como isso acontece.
Meu palpite atual é que tem algo a ver com o repositório git em questão ser privado e hospedar várias joias.
Para corrigir isso, há uma etapa realmente simples:
$ bundle install --path vendor/cache
depois disso, um normal bundle install
funcionará novamente.