If you suffer of this bug and you are tired to wait that Ubuntu’s package manager realize what a monster has packaged for an LTS release then grab this file:

librmagick-ruby_2.11.1-1ubuntu0.1.1_i386

See LP bug #539106

If you want a newer version you can use the 2.13.0 packaged here:
http://www.marcocimmino.net/2010/05/04/librmagick-ruby_2-13-0-2-for-ubuntu-lucid-10-04/