Authentication error when connecting to Heroku PostgreSQL database

Solved it by setting PGSSLMODE (http://www.postgresql.org/docs/9.0/static/libpq-envars.html) on Heroku. It tells PostgreSQL to default to SSL.

$ heroku config:set PGSSLMODE=require