I've used Image::Magick's Trim() method with success before. (though I definitely agree that the PerlMagick docs are not the best).

My only caveat in using the Trim() method is that my use was when i started with a blank canvas and put stuff in the middle somewhere and wanted it auto-cropped down. In your (OP) case, you may need to tell it what to consider as the background color before calling Trim().