Решением этой проблемы было добавление в Heroku домена root (example.com) и www domain (www.example.com). До этого у меня была только запись CNAME с хостом www, указывающим на Heroku. Теперь у меня также есть запись ALIAS с root host '@', указывающим на Heroku.
Спасибо @Ed. Кенберс за то, что указал мне в правильном направлении!