The performance change that was implemented was for product options, it shouldn't have affected the categories. The search for products in a category doesn't matter how many products are in the category. It has to search through all the products to determine which have the category, which is dependent on how fast your database server is as well.