Test code updated to use sample data supplied:

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

chomp (my @data_lines = <DATA>);

# Sort the data lines according to the "Company Name" field and then t
+he "Invoice ID" field.
@data_lines = sort {
    my ($company_name_a, $invoice_ID_a) = (split /\t/, $a)[1, 0];
    my ($company_name_b, $invoice_ID_b) = (split /\t/, $b)[1, 0];
    fc($company_name_a) cmp fc($company_name_b)
        or $invoice_ID_a <=> $invoice_ID_b
} @data_lines;

print "$_\n" for @data_lines;

__DATA__
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:

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]

It ain't the sort. In fact making minimal changes to your sample code to use internal data:

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

# Open the file for input, discard all the header lines, but stop on a
+nd save the column names in an array.
# Read all the remaining lines in to an array and close the file.
my $column_line = "";
$column_line = <DATA> while defined $column_line && !($column_line =~ 
+/Invoice ID/i);
chomp(my @columns = split /\t/, $column_line);
chomp(my @data_lines = <DATA>);

# Sort the data lines according to the "Company Name" field and then t
+he "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
{
    my($company_name_a, $invoice_ID_a) = (split /\t/, $a)[$company_nam
+e_index, $invoice_ID_index];
    my($company_name_b, $invoice_ID_b) = (split /\t/, $b)[$company_nam
+e_index, $invoice_ID_index];
    fc($company_name_a) cmp fc($company_name_b) or
    $invoice_ID_a <=> $invoice_ID_b
} @data_lines;

# Open the file for output, print a new header and the column line to 
+it, then print the now sorted data to it and close the file.
print "Replacement Header Text Here\n\n$column_line";
print "$_\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]

so the issue isn't in any of the code you've supplied or the sample data you have supplied.

Your ball ...