Looks like TabFrame doesn't set up any accessors to allow you to easily change the tab title. You'll need to go spelunking around through the subwidgets to access them after they have been created.

Here's a short demo based on your script with a lot of extraneous stuff cut out.

use strict;
use warnings;
use Tk;
use Tk::TabFrame;

my $tab_mw = MainWindow->new;

my $top_wg = $tab_mw->Label( -text => 'Caption query' )->grid( -row =>
+ 0 );

my $a_tbfr = $tab_mw->TabFrame(
    -font     => '-adobe-times-medium-r-bold--14',
    -tabcurve => 4,
    -padx     => 10,
    -pady     => 10,
    -width    => 50
);

$a_tbfr->grid( '-row' => 1 );

my ( %tabwg, %lbwg );

for my $j ( 1 .. 2 ) {

    # this sets the tab title which can be seen
    my $j_str = "Tab $j";
    $tabwg{$j_str} = $a_tbfr->Frame(
        -caption => $j_str,

    );

    # Find the reference to this particular button (Data::Dumper is yo
+ur friend)
    my $this_button =
      $a_tbfr->{'SubWidget'}{'ButtonFrame'}{'SubWidget'}
      { 'Button_' . $tabwg{$j_str} }->Subwidget('Button');

    # Get tab title
    my $tab_title = $this_button->cget('-text');

    print "Tab title for tab $j - retrieved [$tab_title]\n";

    my $new_title = $tab_title;
    $new_title =~ s/Tab/New/;

   # Change tab title
   $this_button->configure( -text => $new_title );    

    my $lb_str = "Tab " . $j . '_Label';

    my $lb_text = "Text in Label in $j_str";

    $lbwg{$j_str} = $tabwg{$j_str}->Label(
        -text  => $lb_text,
        -width => 100
    )->grid( -row => 2, -column => 0 );

    my $lab_retrieved = $lbwg{$j_str}->cget( -text );

    #print "text given $lb_text wg $tabwg{$j_str} retrieved $lab_retri
+eved\n";

    my $en_str = "Tab " . $j . '_Entry';

    $tabwg{$j_str}->Entry(
        -text  => $en_str,
        -width => 20
    )->grid( -row => 3, -column => 0 );
}

MainLoop;
[download]

Not particularly pretty, but it will get the job done.