When I change sort by type or sort dirrection or select a category the right-hand-side of the category Results page is displaying the wrong number of product counts for each category.
Example: if I select a category which returns only 10 results, the results themselves are fine, but I'm the filters show a count of 2 of products instead of 10 or less.
You can see this page: http://ordme.com/sanitary.html?dir=desc&order=qty_ordered and for example change sort direction or select "Avene" category and see result.
Are you using any module that modifies the product collection? I have seen issues with this in the past and it was due to the modified collection being grouped too early.
I added some new sort types in category page, for example: most_viewed, popularity, qty_ordere ,...
These new sorty types are not attribute I added their queries in this file: app\code\local\Mage\Catalog\Block\Product\List\Toolbar.php