Just looking through the archives to find a better solution than the one that I hacked up, but I couldn't find it!
So, I'll offer my CrapCode to the monestary or something

# FUNCTION: sub_with_str
# Safely do a pattern-matching substitution from two strings (i.e. the pattern
# itself and the substitution string - complete with $1's, etc - are passed in
# as strings. Note that no pattern validity check is done on $old_patt, check
# validity before calling this function. Return the new substituted string.
sub sub_with_str {
    my ($string, $old_patt, $new_patt) = @_;

    my @matches = ( $string =~ m/$old_patt/o );
    for (my $i=1; $i <= @matches; $i++) {
        # Find a dollar sign that is not preceeded by an escape character and
        # $i (a number). For example, $1foo${2}bar\$3 will match on $1 and
        # ${2}, but not on $3. Substitute all occurances with their actual
        # match, which was found above and put in the @matches array.
        my $patt_part = '';
        while ($new_patt =~ s/(.*?)(?:\A|(?<=[^\\]))\$(?:$i|\{$i\})(.*)/$2/) {
            $patt_part .= $1 . $matches[$i-1];
        }
        $new_patt = $patt_part . $new_patt;
    }

    # Get rid of any other $n (found as explained above) since they weren't
    # found as matches.
    $new_patt =~ s/(?:\A|(?<=[^\\]))\$(?:\d+|\{\d+\})//go;

    eval { $string =~ s/$old_patt/$new_patt/o };

    return $string;
}