Taxonomy menu expanded with count
I have scoured the web, banged my head on the keyboard a few times, and finally settled to the fact that there is currently no viable way of achieving this with taxonomy menu.

A simple solution that should work though I have not tried it is using views to achieve the desired effect. I quickly googled that up and came across someone with the same/similar requirement here; http://drupal.org/node/165417. Their questions seem to have been answered and I will therefore try my hand in that direction tomorrow.

Hope this helps.

Edit: Tried using views but had to upgrade to using the 6.x-3.0-alpha3 version. After that it worked perfectly. I used content taxonomy for the relationships with the settings to update core taxonomy vocabularies. Then, using views, I selected HTML list as the style and grouped by the cck taxonomy field.