How about:

my $count = 65; # 65 is the letter 'A' in ASCII
my @original_array = qw(5 100 2 8 40);

my %original_map = map {
   $_ => chr($count++)
} sort { $a <=> $b } @original_array;

my @letter_sequence = map $original_map{$_}, @original_array;
print "@letter_sequence\n";
[download]

Update: Good call, merlyn. Here is one to eliminate the duplicates, I think:

my %seen;
my %original_map = map {
   $_ => chr($count++)
} grep !$seen{$_}++,
sort { $a <=> $b } @original_array;
[download]