Two possible fixes:
1. Move the "my $obj" line to the end ; or
2. add an INIT before each block declaring the class like this:

INIT{ package TestClass;
...
[download]

Update: Updated code. I find using "use base" more readable and safer than messing with @ISA;

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

my $obj=TestSubClass->new;

INIT{ package TestClass;
  sub new {
    my $class = shift;
    my $self = {};
    print "I'm brand new!\n";
    bless $self, $class;
  }
  1;
}

INIT{ package TestSubClass;
  use base "TestClass";
  1;
}
[download]

I use BEGIN rather than INIT since that's what use does and since there are issues with using INIT (although you probably won't encounter them).

The Namespaces for your classes have not been declared, at the time you are attempting to use them.

Wrong. They are. The namespace here are introduced with package and are hence found at compile time.

You should also add a "1;" at the end of each class (Although your code works without that).

And wrong again. The true value is only needed for compilation blocks that are required or used.

add an INIT before each block declaring the class like this:

That will "work" (well, sort of, it may not work if the code is used or required), but for the wrong reasons. Note also that you're using INIT to get the @ISA assignment done at compile time - but now that you've switched to using use base in your update, the assignment to @ISA is done at compile time, making the INIT pointless. In fact, the only thing now left in the INIT blocks to be executed are the useless 1; statements. So you've created a pointless block, for the sole purpose of executing a useless statement. Way to go!

With so many bogus statements, I hope you don't mind getting downvoted (but overall your note still has a postive rating. Another proof that XP means utterly nothing, and certainly cannot be used to determine good posts from utter crap. Or may it just means Perlmonks is mostly visited by people not knowing Perl very well).

The key in the OPs problem is the assignement to @ISA. @ISA is used to determine the inheritance tree, but assignment to @ISA is done at runtime. And the appropriate @ISA hasn't been set at the time new is called.

I have taken your criticisms positively, since I do stand corrected, and did learn from them.

I do take issue with your comment regarding downvoting:
I am here to learn - and try to help others. Occasionally, my apparent lack of understanding of esoteric features of the language has created incorrect recommendations. These nodes are here to be corrected.

My experience is that even incorrect answers that are subsequently corrected by more knowledgeable monks have value - they help clear misconceptions.

     Potentia vobiscum ! (Si hoc legere scis nimium eruditionis habes)

With so many bogus statements, I hope you don't mind getting downvoted

Well, down-voting occurs to a node, not to a poster (and XP is a poor metric of experience ;-)

You should also add a "1;" at the end of each class (Although your code works without that).

Thats because its not needed. You only need the 1;s at the bottom of files that are going to be use()ed.

Great, thank you! Moving the main program beneath the package blocks made it work. I didn't realize the order mattered.

The assignment to @ISA occurs later and thus hadn't been executed before the call to new, so the inheritance wasn't setup.