Of course the correct answer is "use Text::CSV":

#!/usr/bin/perl
use strict;
use warnings;
use Text::CSV;
use 5.016;

my $csv = Text::CSV->new({binary => 1, sep_char => "\t"});
my $row;

1 while $row = $csv->getline(*DATA) and $row->[0] !~ /Invoice ID/;

my @columns = @$row;
my @data_lines;

push @data_lines, $row while $row = $csv->getline(*DATA);

# Sort data according to "Company Name" field then "Invoice ID" field.
my ($company_name_index) =
    grep {$columns[$_] eq "Company Name"} (0 .. $#columns);
my ($invoice_ID_index) = grep {$columns[$_] eq "Invoice ID"} (0 .. $#c
+olumns);
@data_lines = sort {
    fc($a->[$company_name_index]) cmp fc($b->[$company_name_index])
        or $a->[$invoice_ID_index] <=> $a->[$invoice_ID_index]
} @data_lines;

# Print a new header and the column line
print "Replacement Header Text Here\n\n", join ("\t", @columns), "\n";

# then print the sorted data
print join ("\t", @$_), "\n" foreach @data_lines;

__DATA__
Original Header Text    
        
Invoice ID    Company Name
1    SEBASTIAN COMMUNICATIONS
2    MASQUE SOUND
3    SEALEVEL SYSTEMS
4    "MASSTECH, INC"
5    SE INTERNATIONAL
6    "SOUTHEAST SERVO, LLC"
7    "SEALEVEL SYSTEMS, INC."
8    MASTERBILT
[download]

Prints:

Replacement Header Text Here

Invoice ID    Company Name
2    MASQUE SOUND
4    MASSTECH, INC
8    MASTERBILT
5    SE INTERNATIONAL
3    SEALEVEL SYSTEMS
7    SEALEVEL SYSTEMS, INC.
1    SEBASTIAN COMMUNICATIONS
6    SOUTHEAST SERVO, LLC
[download]

Update: and of course Text::CSV should be used to correctly output the data too:

# Print a new header and the column line to it
print "Replacement Header Text Here\n\n";

# print the sorted data.
print render($csv, @columns), "\n";
print render($csv, @$_), "\n" foreach @data_lines;

sub render {
    my ($csv, @cells) = @_;
    
    $csv->combine(@cells);
    return $csv->string();
}
[download]

with modiffied output:

Replacement Header Text Here

"Invoice ID"    "Company Name"
2    "MASQUE SOUND"
4    "MASSTECH, INC"
8    MASTERBILT
5    "SE INTERNATIONAL"
3    "SEALEVEL SYSTEMS"
7    "SEALEVEL SYSTEMS, INC."
1    "SEBASTIAN COMMUNICATIONS"
6    "SOUTHEAST SERVO, LLC"
[download]