Not really a request, this is more for other people if they run into the same problem.
I have Ubercart and it seems to override Taxonomy Breadcrumb, preventing breadcrumbs from appearing on node pages. Granted, I also have Taxonomy Context installed, which has some breadcrumb override code in it (but its turned off), so it might be this module too. Anyway, by simply increasing the module weight for TB to 10, my breadcrumbs appeared correctly.
Just thought I'd share this with everyone.