Got it. Looks like the gem path for a default bluehost install requires some "massaging" to work. :) Following instructions from here resolved the problem for me (relevant parts cut and pasted below as well):
http://www.bluehosttricks.com
A) You will need to have the ability to install gems locally. You can do this by following these directions (via SSH):
1) Add the following lines to your $HOME/.bashrc file (these can be copy and pasted):
export GEM_HOME=$HOME/ruby/gems
export GEM_PATH=$GEM_HOME:/usr/lib/ruby/gems/1.8
export GEM_CACHE=$GEM_HOME/cache
export PATH=$PATH:$HOME/ruby/gems/bin
2) Now modify the applications environment.rb file so that the correct gem path is included. This line should go up at the top before the version of rails is specified:
ENV['GEM_PATH'] = '/path/to/their/home/ruby/gems:/usr/lib/ruby/gems/1.8'
3) Kill off any fastcgi processes that they might have running and the issue should be fixed.
EDIT:
I ended up having to follow ALL the steps in the tutorial I linked above. You have to manually edit the rack fastcgi handler file or else the dispatcher will complain. Apparently this is specific to Rails 2.3.3 (2.3.2 worked fine on BH (allegedly)).