Like this? I get the same result:

my $new_elt = XML::Twig::Elt->new('div');
my $table = HTML::Table->new([[1,2]]);
my $content = decode('iso-8859-1', $table->getTable());
$new_elt->set_inner_html($content);
$new_elt->paste(before => $_);
[download]

Something else to note: If I remove the "TM" from the original XML, everything works; however, as long as it is present, it upsets set_inner_(?:ht|x)ml.