vcTheGuru,
There isn't a bug in the logic. The bugs were in the code, which was untested. To show that the logic is correct. Here is the code working on your data set with very minor bug fixes:

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

my %data;
while (<DATA>) {
    chomp;
    my @col = split /\|/;
    if (exists $data{$col[1]}) {
        $data{$col[1]}{min} = $col[0] if $col[0] < $data{$col[1]}{min}
+;
        push @{$data{$col[1]}{entry}}, \@col;
    }
    else {
        $data{$col[1]}{min} = $col[0];
        $data{$col[1]}{entry} = [\@col];
    }
}
for my $state (sort {$data{$a}{min} <=> $data{$b}{min}} keys %data) {
    for my $entry (sort {$a->[0] <=> $b->[0]} @{$data{$state}{entry}})
+ {
        print "@$entry\n";
    }
}


__DATA__
1|Virginia|Norfolk
2|Virginia|Chesapeake
3|Virginia|Virginia Beach
4|Indiana|Evansville
5|Indiana|Fort Wayne
6|Virginia|Falls Church
7|Indiana|Indianapolis
8|Washington|Seatle
9|Washington|Spokane
[download]

I see that you have a SQL solution not requiring perl.