I am having this same issue on two of my blogs. I have no idea how to fix it.
Mod_rewrite works because my htaccess is allowing my posts and pages to read with pretty permalinks. It is just the categories that are messing up.
When I change my theme to the classic wordpress theme I still get 404 pages or some of the links go to a single post in the category.
When you go to a category and click view it leads to url/category/categoryname but that pulls up 404.
If I put it on the /?p=4 whatever category default it works but I have thousands of posts that have spidered all over various search engines and it would make all those links obsolete to search
I have tried deleting .htacess and reuploading it – it does not work
Any help would be greatly appreciated.