What am I doing wrong? Any idea / hint would be extremely helpful!

Lets look at the error

gtk_tree_store_get_path:
assertion
'iter->stamp == tree_store->stamp'
failed
[download]

So we're dealing with an "get_path" and "iter" and a "store"

So in your code my ($_tree_store, $path, $pattern, $iter) = @_; ...

And you have

my $path = $new_treestore->get_path( $new_treestore->get_iter_first() 
+);
[download]

Next step would be look up the documentation for gtk_tree_store_get_path and look for examples to see what it wants (its clearly not get_iter_first() )

Maybe check your Gtk...versions against bug reports regarding this