Looking at the Crypt::Tea source you'll find the following line at the end of the encrypt routine:

    return &str2ascii( &binary2str(@cblocks) );
[download]

@cblocks seems to be an array of 32-bit ints, which binary2str packs into a string, which in turn is converted into some pseudo-base64 format by str2ascii.  Assuming the string before the str2ascii conversion is what you're interested in (i.e. that this is the same string that Java is dumping as hex), you should be able to retrieve it using the complementary function ascii2str:

use Crypt::Tea qw(ascii2str);

my $encrypted_ascii = ...;

my $str = ascii2str($encrypted_ascii);
# now convert to hex:
my $hex = unpack "H*", $str;
[download]

Of course, this is making a couple of assumptions, so some corresponding example hex/Java and ascii/Perl output would help in verifying those...