Você deve remover todos os rmagick anteriores e, em seguida, ficará bem:
sudo apt-get purge graphicsmagick graphicsmagick-dbg imagemagick-common imagemagick imagemagick-6.q16 libmagickcore-6-headers libmagickwand-dev graphicsmagick-libmagick-dev-compat
sudo apt-get autoremove
sudo apt-get install imagemagick libmagickwand-dev
sudo ln -s /usr/lib/x86_64-linux-gnu/ImageMagick-6.8.9/bin-Q16/Magick-config /usr/bin/Magick-config
gem install rmagick