>> 538
$LOAD_PATH が通ってないのでは？

1. そもそも starruby.so が正しく配置されているか？

自分の場合だと、install.rb を実行すると starruby.so は↓に入ってる。
C:/Ruby19/lib/ruby/site_ruby/1.9.1/i386-msvcrt/starruby.so

まずはそもそもファイルの配置に失敗してないか確認したほうがいいと思う。

2. starruby.so の配置フォルダに $LOAD_PATH が通っているか？

starruby.so がちゃんと配置されてたら、次は

ruby -e 'puts $LOAD_PATH'

の出力に1で確認したフォルダが含まれるか確認する。
含まれてなければ ttp://doc.okkez.net/static/191/doc/spec=2fenvvars.html を参考に環境変数を設定する。