Jag hade samma problem. För att lösa det är det lättare att återställa databasen.
- heroku rake db:reset ('heroku run rake db:reset' om du använder cedar)
- heroku rake db:migrate ('heroku run rake db:migrate' om du är på cedar)
Sedan gjordes migreringen framgångsrikt för mitt fall :)