We are running wpmu. We have about 500 live blogs on our network. Several of our sites have started to see the same problem recently: The category archive page for newly created post categories will 404.
It's not that it says no posts are found for a particular category, it's that it thinks the category itself doesn't exist.
The problem happens...
1) Regardless of theme
2) Regardless of plugins
3) Regardless of category slug
4) Regardless of # posts assigned to the category
5) Only on newly created categories (we noticed it about a month ago and it's still happening -- and seems to be spreading across our network)
6) On the front end -- you can browse categories just fine on the back end.
7) Regardless of how many times I flush the rewrite rules by changing permalink settings
8) On any permalink setting other than default. If I go to default permalink structure, it works fine.
9) Only on categories -- tags work fine.