I feel stupid now.
Actually I had it setup right from the very beginning. I just realised that there are a hundred published products in the "product category" as their parent.
So everything was working as intended, the only problem was that I was under the illusion that all products were organised in their respective categories and the product category was the root of all other categories with no products in it.
The category listing was displaying the categories and when clicked on I could see the product listings, what had me banging my head in the wall were the other "rogue" products and where they were coming from. Which is why I deleted the associated module as a result, thinking it was it causing them to appear.
Moral of the story, several minutes of thinking can save me days of frustration.