Normally I'm a cpan purist, but for Image::Magick, I tend to use my OS installer. If I recall correctly, the Image::Magick perl library and the libmagick have to match exactly and the libmagick installer tries to install it (correctly) for you. I might be thinking of something else. But even if I am, I still try to use my OS perl module installer so everything works without all the effort.

What platform are we talking about here? I'm talking about ubuntu/gentoo/etc...

UPDATE: I imagine redhat has a package for both libmajick and for Image::Magick. I'd start there.