Switch to OpenDNS servers - 208.67.222.222 and 208.67.220.220. Even google NS are down it seems. Heroku works after switching to opendns.
OpenDNS works because, as another poster notes, that, for better or worse, they don't strictly obey TTLs: https://news.ycombinator.com/item?id=12762429