but it doesn't? error: Can't replace an item with its parent!

Clone the image when you push it, then you can replace it

$new_parent->push_content( $img->clone );
$img->replace_with($ new_parent );
[download]

#!/usr/bin/perl --
use strict; use warnings;
use HTML::TreeBuilder;
use HTML::Element;
my $root = HTML::TreeBuilder->new_from_content(
    q{
<p> <img src="1">
<p> <img src="2">
}
);
my @imgs = $root->find_by_tag_name('img');
foreach my $img (@imgs) {
    my $new_parent = HTML::Element->new(
        'a',
        'href' => $img->attr('src'),
        'rel'  => 'lightbox'
    );
    $img->attr( 'class', "thumbnail" );
    $new_parent->push_content( $img->clone );
    $img->replace_with($new_parent);
}
print $root->as_HTML;
$root->delete;    # erase this tree because we're done with it
[download]