If I turn your code into something to exercise your sort the first thing I find is that fc() is missing. Removing that the sort performs as expected:

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

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 /~/, $a)[0, 1];
    my ($company_name_b, $invoice_ID_b) = (split /~/, $b)[0, 1];
    ($company_name_a) cmp ($company_name_b)
        or $invoice_ID_a <=> $invoice_ID_b
} @data_lines;

print "$_\n" for @data_lines;

__DATA__
SEALEVEL SYSTEMS~1
SEALEVEL SYSTEMS, INC.~2
SEBASTIAN COMMUNICATIONS~3
MASQUE SOUND~4
MASSTECH, INC~5
MASTERBILT~6
SE INTERNATIONAL~7
[download]

Prints:

MASQUE SOUND~4
MASSTECH, INC~5
MASTERBILT~6
SE INTERNATIONAL~7
SEALEVEL SYSTEMS~1
SEALEVEL SYSTEMS, INC.~2
SEBASTIAN COMMUNICATIONS~3
[download]

You will notice that I replaced tabs with ~ to make the column separators easier to see.

So maybe you'd like to update my sample code to show your actual problem?

Update: ah, I see fc is "new" as of about Perl 5.16 and I hadn't "turned it on" even though using Perl 5.20 :(. Restoring fc to the sort doesn't alter the result.