Rails apps with version 4 or above has some files under the bin folder namely bundle, rails, rake, setup, spring. But since I had bin folder gitignored, these files dint make it to heroku.

To fix this:

Remove bin from ~/.gitignore
Run bundle install or rake rails:update:bin
Commit your changes with git add . and git commit -m "Add bin back"
Push your changes to Heroku with git push heroku master

Heroku has a detailed article on the same which can be found here.