I had similar trouble installing the Image::Magick Perl module a few months ago, and it seems that we've both stumbled upon the same advice via google. It is accurate advice though, as I have succeeded in installing it only by downloading the tarball and compiling from source. The effort paid off big time too, because it's now way faster than the sub-optimal preinstalled version I was stuck with before.