The latest version, 2, of RMagick requires ImageMagick version 6.4.9 or greater. Unfortunately this version is not available via Aptitude - at least not on the version I am running, which is a few years old now.
The solution, for my purposes, was to install an older version of RMagick:
sudo gem install rmagick -v='1.15.17'
This is the latest version 1 install and works with earlier versions of ImageMagick.