Product categories in the product listing do not show randomly, unless you have some mod operating. Likewise, categories with subcats never show product listing pages unless something custom has been done to the code.
I find it hard to imagine any way the categories sidebox could be affecting the page display logic, unless you have added code to modify the category links. Cat Dressing does not touch the link destination code at all, just wraps them for sidebox display.