Here is a solution that prints out the new file in correct order and doesn't use the existing file at all. It sets the input record separator to $/ = "*\n" and reads in 'chunks' of the file. Also, I found a trailing space at the end of each line which I removed prior to parsing the file. If your data does have these trailing spaces, then they would need to be accounted for. I'm assuming they aren't in the 'new' file, but got there by copy and paste.

The solution uses a Schwartzian transform to process the blocks.

#!/usr/bin/perl
use strict;
use warnings;

open my $new, '<', \<<EOF;
Connection Culv=This is Line3 - New text here 
     333 333 This should be new too 
Conn Culvert Barrel=Culvert3
*
Connection Culv=This is Line1 - New text here 
     111 111 This should be new too 
Conn Culvert Barrel=Culvert1
*
Connection Culv=This is Line2 - New text here 
     222 222 This should be new too 
Conn Culvert Barrel=Culvert2
*
EOF

$/ = "*\n";
print map {$_->[0]}
      sort {$a->[1] <=> $b->[1]}
      map {[$_, /^Conn Culvert Barrel=Culvert(\d+)$/m]} <$new>;
[download]

Connection Culv=This is Line1 - New text here
     111 111 This should be new too
Conn Culvert Barrel=Culvert1
*
Connection Culv=This is Line2 - New text here
     222 222 This should be new too
Conn Culvert Barrel=Culvert2
*
Connection Culv=This is Line3 - New text here
     333 333 This should be new too
Conn Culvert Barrel=Culvert3
*
[download]