You might have a problem when you upgrade WP 3.05 or 3.1.1 to 3.1.2.
There are loads of people complaining about categories not working. I just found this fix and it should help.
Thanks to the developer.
I am not the developer. So if you have any question ask them. :)
Hope this helps some one.