PATHに /usr/local/bin は入っているの?
うちは問題なくインストールできてるんだけど、
ためしにrmagickをアンインストールしてから、
PATHからMagick-configの入っているディレクトリを抜いて
gem install rmagick
してみたら
checking for Magick-config... no
と言われた。