Top Level Categories plugin - So: if you're having trouble with your permalinks after the 3.1 update, make sure to narrow down the problem by deleting plugins that might affect your permalinks (such as category plugins, this multipage thingy, or anything else related to it)
Here is the permanent fix for this. The problem IS caused by the plugin Multipage Toolkit (Current version 2.6).
I didn't have any such related plug-ins and two of my sites, one of which was a pretty fresh install (no plug in and just a modified 2010 child theme), both tanked.
Then I went in and did a TOTAL FROM SCRATCH install of the new 3.1 and I had the SAME EXACT ISSUES.