I'm using Debian Etch and Ruby 1.8.5.  I needed to change require 'md5' to require 'digest/md5' in order for it to work.  This might just be a quirk of my setup, but I thought the information would be useful to somebody.  It works great, have it set to do a nightly/weekly incremental backup to s3.