I had the same issue, I deleted the database from https://dashboard.heroku.com/apps (this was Navy) Added a new PG Database (this was blue)
From the terminal ran:
heroku config
You should see your db url
heroku config:set DATABASE_URL=postgres://your-db-url
Ran
heroku run rake db:migrate
And everything worked. I am still not sure why that happened!