I see the problem using Slackware 12, and Tk-804.027. I experimented a little bit, and found a hacked solution.

#!/usr/bin/perl
use strict;
use warnings;
use Tk;

my $mw = MainWindow->new();
my $frame = $mw->Frame->pack();
populate();

$frame->Button(-command=>\&recompose,
                -text=>'do_it')->pack();

MainLoop;

sub recompose
{       
        $mw->withdraw;
    $frame->destroy();
    $frame = $mw->Frame->pack();
    populate();

        $mw->packPropagate;
        $frame->update;
        $mw->update;
        $mw->deiconify;

}

sub populate
{
    for (1..10)
    {
        $frame->Label(-text=>$_)->pack();
    }
}
[download]

I will point out that your code is bad programming, because you are trying to clean out your labels by destroying the parent frame, still leaves the old labels laying around, and this will cause a memory gain everytime you do it. Using $widget->destroy usually is a bad thing in Tk. You may be able to get away with it, if you run packForget on all children of the frame, then destroy all the children. You are better off, NOT destroying the frame, just empty it then refill it.

#!/usr/bin/perl
use strict;
use warnings;
use Tk;

my $mw = MainWindow->new();
my $frame = $mw->Frame->pack();
populate();

$frame->Button(-command=>\&recompose,
                -text=>'do_it')->pack();

MainLoop;

sub recompose
{       
        my @w = $frame->packSlaves;
    print @w,"\n";
    foreach (@w) { $_->packForget; 
                   $_->destroy;}

    populate();
}

sub populate
{
    for (1..10)
    {
        $frame->Label(-text=>$_)->pack();
    }
}
[download]