I had the same thing: solved it by creating a new Heroku app with Ruby 2.0.0 and looking at the output of "heroku config" of my app vs the new app. Then I noticed that both GEM_PATH and PATH were different, so I did:
$ heroku config:set GEM_PATH=vendor/bundle/ruby/2.0.0
$ heroku config:set PATH=bin:vendor/bundle/ruby/2.0.0/bin:/usr/local/bin:/usr/bin:/bin
And presto, error's gone!
(got the idea from: heroku: bash: bundle: command not found)