How can I customize the upload error message in WordPress?

This is untested, but I think you can just define wp_handle_upload_error in your functions.php file and return custom error messages. If you look at where that function is defined in that file,

if ( ! function_exists( 'wp_handle_upload_error' ) ) {
    function wp_handle_upload_error( &$file, $message ) {
        return array( 'error'=>$message );
    }
}

You can see it first does a test to see if the function is defined, so it would be safe to create another one (of course, in your own code, also check to see if its defined just to be safe). You’ll have some experimenting to do, but hopefully this puts you on the right path!

Cheers~