Since there is always more than one way to do it. Here would be my guess to traverse the file faster:

my $jmp_distance = 100;
my $treshhold = $FOO

my $line = <FILE>;
(my $tstamp, my $rest) = split(/\s+/,$line,2);

#skipping through file by jumping over $jmp_distance lines
do {
  $. += $jmp_distance;
  $line = <FILE>;
  ($tstamp, $rest) = split(/\s+/,$line,2);
} while ($tstamp<=$treshhold)

#since we overshot with the last jump
$. -= $jmp_distance;

while (<FILE>) {
  ($tstamp, $rest) = split(/\s+/,$_,2);
  print if $tstamp > $treshhold;
}
[download]

Of course you can modify this further. For example putting the whole do whileloop in a sub and recursively call it with shorter jmp_distances. that way you could start with a distance of 10000 and then go to shorter distances like 1000, 100, 10 and 1 (1 = condition to break the recursion) if you call the sub with jmp_distance/10.