Hai provato a eseguire la migrazione direttamente da bash all'interno del server heroku? In caso contrario, prova quanto segue...
heroku run bash --app your_app_name_goes_here
bundle exec rake db:migrate
La prima riga di codice apre il terminale di comando bash e la seconda migra il db come al solito.
Questa non sarebbe la soluzione suggerita. Ma, nel caso in cui NON ti interessi perdere i dati nel database, puoi prima provare a ripristinare il database e riprovare. Ancora una volta, non farlo a meno che tu non sia disposto a perdere i dati esistenti!
heroku pg:reset DATABASE
heroku run rake db:migrate
Tuttavia puoi eseguirlo tramite bash come prima.
Spero che questo ti aiuti.