Heroku is trying to install sqlite3 gem even it not being in the Gemfile
When I ran into the problem, turns out I'd forgotten to commit my changes after bundle install. Doh! git status should indicate unstaged changes for the gem files.
I has the same problem and zoltarSpeaks' solution fixed it for me. I had the taps gem installed after reading this article that indicated it would be necessary for pushing from a local sqlite3 to production postgresql: http://batsov.com/articles/2011/10/30/deploying-rails31-apps-on-celadon-cedar/. Turned out I didn't need the taps gem after all, but it was clearly the problem. Removed the reference, bundle update, all systems go.
try deleting Gemfile.lock and run Bundle Install, commit and push