I removed New Relic temporarily and redeployed, and Heroku is working for one of my sites now (also not working for another site though).
Of course its also possible that you just got lucky and Heroku came back up for you when you redeployed. Could be a coincidence.
But the guys at New Relic helped us and fixed the issue, according to them it should not happen anymore.