You need to have menu item for your categories where modules are pulling data from. See below example.
Lets assume you have a category called News and sub categories inside News category. So your menu should look like below.
News
News > Local News
News > Sport News
News > World News.
In above example if you link News Menu item to News Category then rest of sub categories or any modules pulling data from those categories will work fine.
If you have News category as main category, Video as Main category, Games as main category but only News Menu item linked to News category then following will work and not work.
News >
Any modules pulling data from News Category will work, any modules pulling data from Video or Game category will not work.
We are talking about links in module not working as joomla needs "menu id" to transfer users around your website. So at least one main category needs to have a menu item and all sub categories under that category will work fine.
If your problem is not related to above then it can be caused by SEF components or if you import data from your previous website such as joomla 1.5 setups.
See you around...