Perl - 96 (or 71) characters 8784 (or 6259) characters
This is what I came up with in Perl. Went through a few different ways to do it but this seemed shortest from what I can think of so far, at 97 characters.
use List::Util 'shuffle';sub r{($b,@w)=split//,$_[0];$e=pop(@w);return$b.join('',shuffle@w).$e;}
Though, if you cut out the 'use' line (which I guess is valid, since others excluded #include lines in their C programs) I can cut it down further to 71 characters:
sub r{($b,@w)=split//,$_[0];$e=pop(@w);return$b.join('',shuffle@w).$e;}
EDIT It was suggested that I try doing this implementing @tobius' method. This way I got it down to 8784 characters, or by removing the use line, 6259 characters:
use List::Util 'shuffle';sub r{$_[0]=~m/(.)(.+)(.)/;$1.join(''join'',shuffle split//,$2).$3;$3}