Glad you like the tutorial!
Another reader mentioned the Heroku issue as well; sorry it caused confusion. I'll check it out and get back to you. If it continues to be a problem, I suggest moving back to 2.3.5 for now.
Update: It works if you add an explicit gem requirement to RAILS_ROOT/.gems:
rails --version 2.3.8
My hope is that Rails 2.3.8 will Just Work™ on Heroku at some point; I have an email in to them to see if they expect this to be the case.