Creating postgres database on Heroku with Rails 4 error

PG::UndefinedTable: ERROR

I am trying to deploy a Rails 4 app on Heroku with a postgres database. I have precompiled assets, but now when I run:

heroku run rake db:migrate

I get this error:

PG::UndefinedTable: ERROR:  relation "users" does not exist
: ALTER TABLE "users" ADD COLUMN "invited_by_user_id" integer
rake aborted!

Commonly suggested solutions on Stack Overflow:

I have tried resetting the database with:

heroku pg:reset

The database resets, but I still can't run db:migrate.

I have also tried:

heroku run db:setup

but I get an error that says:

FATAL:  permission denied for database "postgres"
DETAIL:  User does not have CONNECT privilege.

I was using Rails 4.1.8, and saw this question which suggested maybe I needed to update to rails 4.1.9 or above, but even now that I'm using Rails 4.2.2, no luck.

Additional possibly relevant info:

Connecting to the postgres database on heroku with

heroku pg:psql

then listing the databases with '\l' gives me a long list of databases with cryptic names:

 Name      |     Owner      | Encoding |   Collate   |    Ctype    |         Access privileges         
----------------+----------------+----------+-------------+-------------+-----------------------------------
 d100o5a2gii5he | rdxtahlqikernc | UTF8     | en_US.UTF-8 | en_US.UTF-8 | rdxtahlqikernc=CTc/rdxtahlqikernc
 d102ehvv3umqam | ibuffadisyolrb | UTF8     | en_US.UTF-8 | en_US.UTF-8 | ibuffadisyolrb=CTc/ibuffadisyolrb
 d103n2kea6j5sa | tzzkfcinullytw | UTF8     | en_US.UTF-8 | en_US.UTF-8 | tzzkfcinullytw=CTc/tzzkfcinullytw
 d10597iiu347nk | eltovdzaxajtiu | UTF8     | en_US.UTF-8 | en_US.UTF-8 | eltovdzaxajtiu=CTc/eltovdzaxajtiu
 d108g0imdgn865 | pvzysfivyhcnaa | UTF8     | en_US.UTF-8 | en_US.UTF-8 | pvzysfivyhcnaa=CTc/pvzysfivyhcnaa
...

 dvs2j8tkv153m  | zjefhzzizozpwy | UTF8     | en_US.UTF-8 | en_US.UTF-8 | zjefhzzizozpwy=CTc/zjefhzzizozpwy
 postgres       | postgres       | UTF8     | en_US.UTF-8 | en_US.UTF-8 | postgres=CTc/postgres
 template0      | postgres       | UTF8     | en_US.UTF-8 | en_US.UTF-8 | =c/postgres                      +
        |                |          |             |             | postgres=CTc/postgres
 template1      | postgres       | UTF8     | en_US.UTF-8 | en_US.UTF-8 | postgres=CTc/postgres
(4787 rows)

I'm not sure exactly how to interpret that.

I am relatively new new to Rails, but have successfully setup several databases on Heroku in the past. Following the Heroku documentation hasn't helped, and I'm not sure where to go from here.

How can I get db:migrate to complete without errors?

NOTE: I solved this just after posting. See answer below.