Nunca he usado Heroku con PHP, siempre con Ruby y frameworks como Rails y Sinatra y la verdad es sumamente fácil...
Por lo que veo el problema creo que es que Heroku no soporta PHP, segun su web principal y el DevCenter solo soporta Ruby, Node.js, Clojure, Java, Python y Scala.
En ese caso te recomiendo usar
AppFog el cual si soporta PHP. Al igual que con Heroku, solo lo he usado para apps Ruby, pero por lo que he leido en su documentacion, no es muy distinto el implementar una app PHP en AppFog.
Saludos.