Internal Server Error every time I push up my Wordpress Project to Heroku

Question

We use Heroku to deploy our Wordpress project. However, everytime we push up it seems that all of the links bring the user to an Internal Server Error page. The homepage works.

Updating the permalinks (using the pretty permalinks for %postname%) solves this issue.

What we believe to be happening is that when a user hits: www.example.com/menu the permalinks haven't been updated yet, so the user sees an Internal Server Error. If you go to www.example.com/?p=2 you get redirected to www.example.com/menu but the page shows an Internal Server Error again.

Right now we have to update the permalinks every time we push up a new version of the site.

Anyone else have this problem and what did you do to solve it?

Much appreciation.