We moved all but one of our Rails apps off of Heroku precisely because of the frequent downtime -- or, rather, that was the last straw; there were other issues, notably the difficulty in debugging production issues, that had us already debating such. Heroku has gotten somewhat better, but it's still down far more than anything else that we use. (And we have services spread across Linode, Rackspace, AWS and the mentioned one app on Heroku.)
You'll have better uptime in most cases with a standard nginx / passenger setup on a $20 VPS than you will with Heroku.