That must be it.
Using: W3 Total Cache, Omniture - SiteCatalyst, JSON API, Google News Sitemap Feed With Multisite Support, and Embedly.
W3 Total Cache is a pain to re-enable for each blog. I'll do some testing next week and try to figure out which two conflict.
What was strange is that some of the blogs wouldn't allow the creation of new categories and others would. It may have been blogs we added after one of the conflicting plugins was added. I'll try to be more scientific about tracking down which ones interact badly.
To add to the complication some are activated at the network level and others at the blog level.