I had the same problem. To solve it, resetting the database is more easier.
- heroku rake db:reset (‘heroku run rake db:reset’ if you’re on cedar)
- heroku rake db:migrate (‘heroku run rake db:migrate’ if you’re on cedar)
Then, migration was done successfully for my case 🙂