I figured it was probably a Content-Type problem, but could not put my finger on it.

Right. A message with attachment is Content-Type: multipart/mixed where the parts are divided by the boundary. - Instead of repeating $smtp->datasend() statements over and over as in alejandro's example, one could make use of HERE-documents. The parts begin after the boundary line followed by the sub-headers which define the type of the part and an empty line. It is good practice to announce the type of mail to non-MIME-aware clients before any part starts.

...
use MIME::Base64;
use Time::HiRes qw(gettimeofday);
...
my $filename = "some.pdf";
my $pdfbody = do {
    local $/;
    open my $fh,'<', $filename or die "pdfread: $!";
    <>;
}; 
my $boundary = encode_base64( join('',gettimeofday), ''); # 
$smtp->datasend(<<"EOH");
From: $from
To: $to
Subject: $subject
Content-Type: multipart/mixed;
              boundary="==$boundary";
MIME-Version: 1.0
Return-Path: postmaster\@your-domain.tld

This is a message in MIME format.
Please use a MIME capable mail client to read this message.

--==$boundary
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit

Hello $recipient,
this is the mail body as displayed by your MIME capable mail client.
blah blah

The PDF file $filename is sent with this message as attachment.

regards,
$sender

--==$boundary
Content-Type: application/pdf; charset=utf-8; name="$filename"
Content-Disposition: attachment; filename="$filename"
Content-Transfer-Encoding: 8bit

$pdfbody

--==$boundary--
EOH
[download]

This avoids repetitions and is easier to maintain.

update: added last boundary delimiter as per afoken's comment