Looking at the Time::Local documentation, I see the following:

The timelocal() and timegm() functions perform range checking on the input $sec, $min, $hour, $mday, and $mon values by default.

So, I would just exploit that and hand the parts of the date to, say, timelocal, and see if it accepts these values as valid or not:

my ($sec,$min,$hour) = qw( 0 0 12 );
my ($mday, $mon, $year) = qw(11 5 2007);
$mon--; # because that's how unix/C treat the month value

eval {
    my $dummy = timelocal($sec,$min,$hour,$mday,$mon,$year);
};
if (my $err = $@) {
    print "This is an invalid date.";
} else {
    print "Yay";
};
[download]

Splitting up $userdate into the parts making up the day, month and year is left as an exercise to the reader.