After getting a message that a module which was definitely installed was not found, a colleague eventually had the idea of checking the require path by running
puts $: in irb. Sure enough there was a different module with the same name earlier in the path than the one gem had installed. I uninstalled Ubuntu's own libxml-ruby and libxml-ruby1.8 and all was well. Interestingly, though, one of these (I forget which) was required to install the gem to begin with -- I guess it needed some header it provided. There's no separate -dev package (at least in this old release of Ubuntu).