Al principio parece fácil correr Rails en Ubuntu con Heroku, pero da ciertos errores menores fáciles de solucionar. Al empezar es bastante directo:
sudo apt-get install ruby
sudo apt-get install rubygems1.8
sudo gem i rails

Ups.. no anda, muestra un error gems... probamos con la aplicación preinstalada en ubuntu:

sudo apt-get install rails

Lo cuál nos instala Rails v2.3.2, que para seguir el tutorial sirve pero nos faltan dependencias y no llego a hacer:
gem i heroku
como para que me dé error de que no encuentra la gem:

ERROR: Could not find gem heroku locally or in a repository

¿Qué ocurre? ¿Error con gems? Sí, y no basta con hacer update, leyendo por ahí, se ve que hay que forzar la actualización de Gems pero la única forma posible es haciendo:
$ sudo gem install rubygems-update
$ sudo /var/lib/gems/1.8/bin/update_rubygems
$ gem -v
1.3.7

Esto nos installa el update como un archivo más de ruby gems, el cuál tenemos que ejecutar. Seguidamente verificamos la versión de gem. Ahora estamos en condiciones de instalar Heroku:

sudo gem i heroku
heroku help

Voilà, Heroku instalado. Si ya tenemos configurada la PKI podemos empezar con:
heroku list
Heroku
o bien seguir la guía de Inicio Rápido