I recently encountered a problem where categories on this blog suddenly stopped working. Apparently it’s quite a common problem where both categories and tags stop working. In my case it was only categories. Tags continued to work perfectly.
As it turns out, the cause of the problem was a plugin called Advanced Permalinks. I had installed this when changing permalinks from date based to just /%postname%/ as the performance issues associated with this type of permalink was fixed as of WordPress 3.3.
So, if you have problems with just categories not working, try turning off Advanced Permalinks.
Went back to default under permalinks and categories now working. Thanks