I got this error message while wiring up private gems bundled via github:

Your bundle is locked to <…>, but that version could not be found in any of the sources listed in your Gemfile. If you haven’t changed sources, that means the author of <…> has removed it. You’ll need to update your bundle to a version other than <…> that hasn’t been removed in order to install.

Originally the problem appeared due to permissions issues: my server didn’t have access to my private repos. However, the above error appeared once the permissions issues were resolved.

I verified that git had the requested version of the gem, in the requested branch.

I found that running bundle update in production solved it. I modified my deploy script, capistrano in this case, to run the following during deploy:

bundle update