I stumbled upon your question while searching for Image::Magick information. Two tips:
- Perl gives the "Can't locate" error when it can't properly load the module - for instance, if the Perl module (Magick.pm) exists, but refers to a library file or DLL which can't be found or which gives an error during initialization. I'm sure there's a better way to debug these problems than the one I use, but I've used SysInternals' Process Monitor in the past to track down the referenced DLLs which were having problems loading properly.
- The quickest way to get PerlMagick on Windows is to get the binary release from ImageMagick.org. The installer searches for ActivePerl, and - if found - automatically installs PerlMagick's modules into the correct place.
Hope that helps (if you haven't figured out the problem in the last three months!)