Did I hear golf?

sub a{
$_=pop;
$i+=$++1while s/Re:\^?(\d*) *//;
"Re:^$i $_"
}
[download]

That weighs in at 50 chars, and it handles cases such as: "Re: Re:^3 title" by adding the 2 "Re:"s and the 3, since three "Re:"s have been taken out before, which was denoted by the ^3.

The 15 year old, freshman programmer,
Stephen Rawls