Reposted from "IMPORTANT: WordPress 3.1 Update Information" thread per James' request.
Global Site Search plugin is not 3.1 compatible. Spent several hours narrowing down which plugin was the culprit and between network activations + regular site plugins + mu-plugins + drop-ins etc, troubleshooting can be quite a bear on a complex multi-site install these days
Turns out that the Global Site Search plugin causes the horrible 3.1 %category% permalink 404 of doom issue. Verified this by rolling back to 3.0.4 and everything worked. Roll forward to 3.1 and I could not access site.com/category/category_name archives, but got a 404 instead. Disabled all plugins in 3.1 and reset permalinks. Worked. Added plugins 1 at a time and it breaks on Global Site Search. Remove Global Site Search, reset permalinks > works. Add Global Site Search back into mu-plugins folder > doesn't work.
Also - it is only the main root site that seems to be affected. Other sites in the network do not have the same issue even with 3.1 and Global Site Search active in mu-plugins.
Maybe it's theme related. For what it's worth, Global Site Search is working fine for us and all /category/categoryname/ permalinks are rendering properly with the following network activated plugins...
Network Activated Plugins: Admin Ads, Admin Help Content, Anti-Splog, Avatars, Blogs Directory, Invite, Members Directory, Post Indexer, Recent Comments, Recent Global Posts Feed, Recent Global Posts Widget, Sitemaps and SEO – WordPress Multisite Style, Supporter, Terms Of Service, The WordPress Popup Plugin Update Notifications Main Site Theme: WPMU Nelo – Special CMS Frontpage Theme
However, I'm pretty sure I tried the default theme and had the same issue, but that was in the wee morning hours and memory is foggy. Maybe conflict with a combo of plugins? Anyway haven't had time to go back and play more. But I think I ruled theme out also because all sites (except root site) still work with the same theme as the root.... and global site search is network activated, so it should impact them too?
Whatever the root cause, the combo of WP 3.1 and Global Site Search break the permalinks for category and tag archives. I have my permalink structure set to /%postname%/ but nothing different for the /category/ and /tag/ structure. If I remove either factor (WP 3.1 or Global Site Search) everything works like normal. Add either one to the mix - the combo causes 404's on cats and tags.
Open to trying other things! (though I'm not sure I'm in a hurry to get back to 3.1... not liking the separate network admin thing, especially for plugin management.