Did something similar recently, and adding dynos didn't help. Then I realized I was limited by my own bandwidth; both my co-founder and I could hammer heroku from our homes and still see the same maximum throughput individually.
Our main take-away was that their caching layer was really effing fast.