Thanks for that reply - yes if I were distributing things using a Makefile.PL then this would be a non-issue. But right now I distribute things as Debian packages, and raw .tar.gz files.
(This particular case came up when I made a new release of my chronicle blog compiler.)
Changing my test case to read as follows still fails though:
#/usr/bin/perl -w
#
use strict;
use warnings;
no warnings "all";
use Test::More qw( no_plan );
BEGIN{ use_ok( 'CGI' ); }
BEGIN{ use_ok( 'Date::Format' ); }
BEGIN{ use_ok( 'POSIX' ); }