I can't reproduce your or Ikegami's problem, works fine for me.¹

  DB<124> $a=42; $a =~ s/(.)(.)/(sort { $a <=> $b } $1,$2)[0]/e ;$a
 => 2

  DB<125> $a=42; $a =~ s/(.)(.)/(sort { $a <=> $b } "$1","$2")[0]/e ;$
+a
 => 2

# UPDATE with /g flag

  DB<107> $a=4215; $a =~ s/(.)(.)/(sort { $a <=> $b } $1,$2)[0]/eg ;$a
 => 21

  DB<108> $a=4215; $a =~ s/(.)(.)/(sort { $a <=> $b } "$1","$2")[0]/eg
+ ;$a
 => 21
[download]

Maybe your match part isn't doing what you think it should?

Otherwise which Perl version are you using?

mine:

$ perl -v

This is perl 5, version 14, subversion 2 (v5.14.2) built for i686-linu
+x-gnu-thread-multi-64int
[download]

¹) though I agree with others that this approach is overly complicated.