I have a WPMU site with hundreds of blogs on it. We are on 3.4.2 and this is the first time I'm seeing this issue within a few of my sites.
Basically, what happens is that I'll create a new category and then when I click on it from the sidebar where all the categories appear, it 404's. Also, this happens when I add a new article to the new category.
This is happening on a few of my sites now. What's interesting to note is I cannot reproduce the issue on test even though test is more of less a direct clone of my live envrionment. The only difference between live and test is that I use a domain mapping plugin on live. Also, I have 6 memcached nodes/servers (AWS) whereas my test area only has one. My live area has 5 app servers and my test area has one. We have the multi-DB plugin installed in both environments. Aside from those differences, the plugins are exactly the same as is the code base.
The issue happens:
--> Regardless of category slug
--> Regardless of # posts assigned to the category
--> 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)
--> On the front end -- you can browse categories just fine on the back end.
--> Regardless of how many times I flush the rewrite rules by changing permalink settings
--> On any permalink setting other than default. If I go to default permalink structure, it works fine.
--> Only on categories -- tags work fine.