Installing rmagick 2.13.1 with graphicsmagick on Ubuntu 10.04
Try to install again after installing libmagickwand-dev.
apt-get install libmagickwand-dev
The dev packages are really helpful
sudo apt-get install libmagickcore-dev libmagickwand-dev
This helped me:
sudo apt-get install imagemagick libmagickcore-dev