To get a taxonomy node count correctly for taxonomy terms you need to do the following:

• In Fields: add Taxonomy term: Name
• In Relationships, add a Taxonomy term: Content with term
• Add a contextual filter for Taxonomy term: Name
  • 3a. Choose 'Display a summary'
  • 3b. Choose 'Display Record count with link'. Also set base path if you want the taxonomy page to be linked correctly.

In the source code is an example using Taggs Category supplied with the drupal defualt install.