If using a View, the view should be used rather than taxonomy_term_count_nodes

I could be missing another ticket open for this.

What menu items show and optionally the printed number representing how many nodes will show within them, is being determined by taxonomy_term_count_nodes. This is fine unless you have selected to use a custom View.

For example if you use a custom view that only shows nodes created today, you can end up with empty menu items, and numbers that don't make sense.