Speaking to your purpose and not your mechanics, after further experimentation I came up with this:

use strict;

my $s = '<p>something something</p>
<h2>blah </a> blah blah </h2>
<p>something something</p>';

my $start = '<h2>';
my $end = '</h2>';

my $first = index($s,$start);
my $last = index($s,$end,$first);

substr($s, $first, $last-$first+length $end) = '<h1>'.substr($s,$first
++length $start,$last-$first-length $start).'</h1>';

print $s;
[download]

Which simply finds the first occurence of $start, then finds the next occurence after that of $end, and replaces that sub string with a new sub string. It's not quite as nice looking, but it doesn't break with random chars in between the start and end nodes. As it is now, it only replaces the first occurence of the start/end tags, but if you wanted to do it generally, you would just need to keep track of where ever the last $start or $end tag (your preference) was found and use that as the starting point for the next index.

At the moment the only bug I see is nesting, which would require slightly more complicated code, probably something along the lines of finding the first occurence of $start, then finding the next occurence of $end and then checking if another $start appears between them, if so, skip that $end tag and move on. That would of course break the current ability to repeat $start as many times as you want and just end with a single $end tag, and so would require 'properly nested data', which can probably be considered a feature =]

This was mostly 'off the cuff' code and by no means thoroughly tested, so if anyone else sees any major flaws I would be interested in hearing them.

Hrm, perhaps something like:

while(1)
{
    if( index( substr( $s, $start_pos, $end_pos-$start_pos ), $start_t
+ag ) != -1 )
    {
        $end_pos = index( $s, $end_tag, ++$end_pos );
    }
    else
    {
        last; # $end_pos is good
    }
}
[download]

For the nested loops, assuming the existience of certain vars to simply things. This isn't tested at all however, and should be treated mostly as pseduo code.