The most obvious problem is your chcking logic. If you want to
sequentially check several things you need:

sub checkit {
    if {}
    if {}
    if {}
  return;
}

not this (which is what you have) 

sub checkit {
    if {}
    elsif {}
    else {}
  return;
}

Your sub exits the if/elsif/else statement if $min is non zero and 
also  $len < $min. BTW: Why you use two ifs here instead of an and
to eval these two conditions is beyond me. This is fixed below:

sub paramCheck
  # Returns "" if no error or description of problem(s).
  {
    my $lbl = shift;  # Field name for error messages
    my $val = shift;  # Value received from the CGI query
    my $min = shift;  # Minimun length; Use >0 for required fields
    my $max = shift;  # Maximum allowed length
    my $pat = shift;  # Regex to validate the data against.
    my $msg = shift;  # Explanation added to error if Regex fails.
    my $err = "";     # Holds error message
    my $len = length( $val );

    if ( $min and $len < $min ) {
       { $err .= wes( "$lbl cannot be blank." ); }
    }
    if ( $len > $max ) { 
       my $s = $len == 1 ? "" : "s";
       $err .= wes( "$lbl is currently $len character$s; " . 
                    "; it can only be $max character$s long." );
    }
    if ( $val !~ $pat ) { 
        $err .= wes( "$lbl contains invalid characters; " . 
                     "it can only hold $msg." );
    }
  return $err;
}

I assume you are assigning $pat as so (it won't work otherwise):

$pat = m/foo/;

Run this if you are unsure of what I am getting at:

$pat = "m/foo/";
print "foo1\n" if "foo" =~ $pat;

$pat = m/foo/;
print "foo2\n" if "foo" =~ $pat;

$pat = qr/foo/;
print "foo3\n" if "foo" =~ m/$pat/;

Passing $pat into a sub is no problem using either of 
the second two methods above. The first does not work
period as you will see if you run it.

happy coding

tachyon