Applying my 2 cents 4 years too late. I came here tonight looking because I had the same problem as the original poster and after some thinking on the responses I came up with something I didn't see in the other answers (hopefully I read them all, there were alot).

anyhoo,...

ApplyRegExRename('witch(\d\d\d)\.jpg','witch_%02d.jpg');

# param 1 = regex expression for find
# param 2 = sprintf expression for replacement
sub ApplyRegExRename # supports up to 5 caught matches within the patt
+ern
{
    my $regex = shift;
    my $repl = shift;
...
        my $file2 = $file;
        $file2 =~ s/$regex/sprintf($repl,$1,$2,$3,$4,$5)/e;
        print "renaming: $file to $file2\n";
...
}
[download]

Works good enough for my purposes.

Keep in mind you can be tricky with sprintf expression to reorder how your $1-n vars are consumed as well.