Any ideas?

Yes, use the source Luke. The error is a croak() so it identifies the caller:

Entity.pm

=1849=    ### Get the encoding, defaulting to "binary" if unsupported:
=1850=    my $encoding = ($self->head->mime_encoding || 'binary');
=1851=    my $decoder = best MIME::Decoder $encoding;
=1852=    $decoder->head($self->head);      ### associate with head, i
+f any
[download]

OK so the issue is with the call (better written as) MIME::Decoder->best($encoding)

Decoder.pm

sub best {
    my ($class, $enc, @args) = @_;
    my $self = $class->new($enc, @args);
    if (!$self) {
    usage "unsupported encoding '$enc': using 'binary'";
    $self = $class->new('binary') || croak "ack! no binary decoder!";
    }
    $self;
}
[download]

So you see that we try to create an object with the passed encoding, and if the call to new returns undef we warn about the unsupported usage and default to binary. Regardless of the initial $enc (could be binary or an unknown) we know we must be calling new() with an enc type of binary and that call is returning false. That's how we get to croak.

sub new {
    my ($class, @args) = @_;
    my ($encoding) = @args;
    my ($concrete_name, $concrete_path);

    ### Coerce the type to be legit:
    $encoding = lc($encoding || '');

    ### Get the class:
    ($concrete_name = $DecoderFor{$encoding}) or return undef;
    ($concrete_path = $concrete_name.'.pm') =~ s{::}{/}g;

    ### Create the new object (if we can):
    my $self = { MD_Encoding => lc($encoding) };
    require $concrete_path;
    bless $self, $concrete_name;
    $self->init(@args);
}

### The stream decoders:
%DecoderFor = (

     ### Standard...
    '7bit'       => 'MIME::Decoder::NBit',
    '8bit'       => 'MIME::Decoder::NBit',
    'base64'     => 'MIME::Decoder::Base64',
    'binary'     => 'MIME::Decoder::Binary',
    'none'       => 'MIME::Decoder::Binary',
    'quoted-printable' => 'MIME::Decoder::QuotedPrint',
    # snip
);

sub init {
    $_[0];
}
[download]

Now I simply don't see how you can possibly get that error!!! Even if you delete the Binary.pm module! The only way that the new function can return undef is if 'binary' is not in %DecodeFor, or if $self->init(@args) returns undef (it should not for the obvious reason that it returns $self). All I can suggest is putting some debugging warns into the new function to localise the bug and checking the content of %DecodeFor with Data::Dumper just prior to its use. It is a global so perhaps something is stomping on it. That is the only really logical explanation. I can't replicate it on my system, nor would I expect to be able to.