Yo tuve el mismo problema. Para solucionarlo, resetear la base de datos es más sencillo.
- heroku rake db:reset ('heroku run rake db:reset' si estás en cedar)
- heroku rake db:migrate ('heroku run rake db:migrate' si estás en cedro)
Luego, la migración se realizó con éxito en mi caso :)