Well, your code (the header/error part of it) ran properly for me. Here is a slightly more explicit version you might try on your own server. I'm running Apache 2.

use warnings;
use strict;
use CGI qw(:standard);
$CGI::POST_MAX = 2_000;  # play nice

my $uploaded_file = param('upload');

if ( not $uploaded_file and cgi_error() ) {
    print
        header(-status=>'200 OK'), # this might help, or not...
        start_html(-title=>'TOO BIG'),
        h2("Why are you disrespecting me with that file size?");
}
else
{
    print
        header(),
        start_html(-title=>'Just right!'),
        h2("I'm Okay, You're not so bad.");
}

print
    start_multipart_form(),
    filefield(-name=>'upload'),
    submit('Upload'),
    end_form(),
    end_html();
[download]