Use the (??{}) construct and it's pretty easy:

#!/usr/local/bin/perl
use warnings;
use strict;
use Date::Simple;

$|++;
my $good_date = sub {
    my ($year,$month,$day) = ($1, $2, $3);
    my $date = do { 
        no warnings 'uninitialized'; 
        Date::Simple->new($year,$month,$day) 
    };
    return $date ? qr{(?=)} : qr{(?!)};
};

# CCYY-MM-DD[tz]
my $pat = qr /^(\d\d\d\d)-(\d\d)-(\d\d)(??{$good_date->()})/;
while (<DATA>) {
   chomp;
   print "$_ ", /$pat/ ? "matches\n" : "does not match\n";
}


__DATA__
1968-04-02
-0045-01-01
11968-04-02
1968-04-02+05:00
1968-04-02Z
invalids to follow
68-04-02
1968-4-2
1968/04/02
04-02-1968
1968-04-31
[download]

And the output:

1968-04-02 matches
-0045-01-01 does not match
11968-04-02 does not match
1968-04-02+05:00 matches
1968-04-02Z matches
invalids to follow does not match
68-04-02 does not match
1968-4-2 does not match
1968/04/02 does not match
04-02-1968 does not match
1968-04-31 does not match

I gave a simplified example to show you how it's done, but you'll want to flesh out that regex more.

Anything can be done in a regex if you use /e, ?{ }, or ??{ }. I just don't promise it will be easy :)

If you want easy, look at Date::Manip or one of the other multitude of Date/Time modules on CPAN.