Perl - 97 characters (or 71 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;}