Here's my shot at it; 68 chars:

sub c {
($_,$a)=@_;                                   
map{$h{$_}?$h{$_}:do{$h{$_}=(split//,$a)[$i++]."\0"}}/./g
}
[download]

Update:

Here's another at 66. This one takes a completely different approach--it removes all duplicates of letters(the long part), then does a simple translation on them (the easy part). Here it is:

sub c {
($_,$a)=@_;$b=$_;  
1 while$b=~s/(.)(.*?)\1/$1$2/g; 
eval"y/$b/$a/";    
$_ 
}
[download]

Update2:Good catch tilly. This makes it too long to contend, but here's the revised version:

sub c {
($_,$a)=@_;$b=$_;  
1 while$b=~s/(.)(.*?)\1/$1$2/g; 
eval"y/\Q$b\E/\Q$a\E/";    
$_ 
}
[download]

The 15 year old, freshman programmer,
Stephen Rawls