I am having the same problem,
My hosting provider (hostgator.com) says they have it, and I verified.
I dont have ssh access so I wrote a script that does:
which mogrify >> /home/user/output.txt
and it sure enough says:
But during the install, it fails and says it cant find mogrify.
I also had another problem with Esvon classifieds where it needed convert
(part of ImageMagic) and HostGator support said it is in /usr/bin
But the install failed??!?!
I will be investigating this and let you know if I come up with anythnig.