psql: SSL error: certificate verify failed
Ok. I figured out that in my system, somehow there is a root.crt file in the ~/postgresql dir. The .crt file made the whole problem (it wasn't certificated to Heroku) and when I deleted it, the connection worked.
FYI