Turns out this was due to the fact HTTP::Message::decodable wasn't available in the version of libwww-perl that is packaged with Debian Lenny. It was introduced in 5.814 but the version package with Lenny is 5.813. To fix I upgraded the version using CPAN: