Cannot push to Heroku (gemfile.lock issue)

Summary:

When pushing to my staging app, Heroku complains that bundle install failed and that I need to run bundle install elsewhere and version the resulting Gemfile.lock. The problem is that I've already done this and committed it.

How do I fix this?

Issue:

Due to some inherited awfulness at work, I had to debug and fix several things in production. Everything's working now, but this means our master branch is ahead of staging by 10+ commits, including some gem changes. I merged them and attempted to push to my staging app on Heroku.

However, I didn't run bundle install after merging in the changes (shame on me), so Heroku correctly complained.

To fix this, I ran the standard:

bundle install
git add Gemfile.lock
git commit -m "Updated gem bundle"
git push staging

However, Heroku is still complaining about Gemfile.lock:

Counting objects: 228, done.
Delta compression using up to 6 threads.
Compressing objects: 100% (179/179), done.
Writing objects: 100% (192/192), 24.38 KiB | 0 bytes/s, done.
Total 192 (delta 127), reused 0 (delta 0)
remote: Compressing source files... done.
remote: Building source:
remote:
remote: -----> Using set buildpack heroku/ruby
remote: -----> Ruby app detected
remote: -----> Compiling Ruby/Rails
remote: -----> Using Ruby version: ruby-2.2.2
remote: -----> Installing dependencies using bundler 1.11.2
remote:        Running: bundle install --without development:test --path vendor/bundle --binstubs vendor/bundle/bin -j4 --deployment
remote:        You are trying to install in deployment mode after changing
remote:        your Gemfile. Run `bundle install` elsewhere and add the
remote:        updated Gemfile.lock to version control.
remote:        You have deleted from the Gemfile:
remote:        * ruby-drupal-hash
remote:        Bundler Output: You are trying to install in deployment mode after changing
remote:        your Gemfile. Run `bundle install` elsewhere and add the
remote:        updated Gemfile.lock to version control.
remote:
remote:        You have deleted from the Gemfile:
remote:        * ruby-drupal-hash
remote:  !
remote:  !     Failed to install gems via Bundler.
remote:  !
remote:
remote:  !     Push rejected, failed to compile Ruby app
remote:
remote: Verifying deploy...
remote:
remote: !       Push rejected to redacted-staging.
remote:
To https://git.heroku.com/redacted-staging.git
 ! [remote rejected] master -> master (pre-receive hook declined)
error: failed to push some refs to 'https://git.heroku.com/redacted-staging.git'

Also:

Gemfile.lock is not in .gitignore
bundle install runs fine, and does not update any gems (as I've run it several times now).
To verify my sanity, I checked git status and git log to ensure I actually added and committed the changes; I'm apparently not crazy (though please correct me if i'm wrong).

To reiterate:

I have already run bundle install and added & committed Gemfile.lock

How do I fix this?

What am I missing?

Update:

I've tried

running bundle update which updated 26 gems; committing the new Gemfile.lock and pushing results in the same error.
Deleting and re-bundling produces an identical Gemfile.lock. Adding a newline and pushing results in the same error.
Removing Bundler's version info from Gemfile.lock and pushing results in the same error.
I even re-addded the ruby-drupal-hash gem, ran bundle install, and pushed the new Gemfile and Gemfile.lock files. Interestingly, the error message about me deleting ruby-drupal-hash persisted despite it being present again.

Solution

The answer was deceptively simple (of course):

git push staging staging:master

The issue was that I was on the staging branch and needed to update my Heroku staging server's master branch.

Shame on me for overlooking something so obvious! ... and shame on Heroku's decidedly unhelpful output.