dr_jgbn,
See if this untested code isn't what you are looking for:

#!/usr/bin/perl -w
use strict;

open(INPUT,"input.txt") or die "Unable to open input file : $!";
open(OUTPUT,">output.txt") or die "Unable to open output file : $!";
select OUTPUT;

my %data;
my @order;

while (<INPUT>) {
   chomp;
   my @field = split /\t/;
   push @order , $field[0] unless (exists $data{$field[0]});
   push @{$data{$field[0]}} , @field[1 .. $#field];
}
foreach my $key (@order) {
   print join "\t" , $key , sort @{$data{$key}};
   print "\n";
}
[download]

You may want to look at this for ideas how to accomplish this without reading everything into memory.

Cheers - L~R

Update: Now tested and verified to be correct