I had a simular problem when I installed RMagick on solaris.

The problem was that the gem install didn’t show a real error but the install wasn’t completed.

(I forgot to include the path to make cmd in my $PATH)

So verify that you have a RMagick.so and have a look at <your_gemdir>/rmagic-xx.xx/gem_make_out