Custom Permalinks stopped working for me too upon upgrade to 3.1. Found that differences in the permalink code in wp-includes/canonical.php were the problem, specifically the section of code beginning with
// These tests give us a WP-generated permalink
and ending before
* Attempts to guess correct post based on query vars.
Copying the code from that section found in the previous upgrade of WordPress wp-includes/canonical.php and pasting it over the WordPress 3.1 wp-includes/canonical.php code section fixed the problem. I now have a full clean, working WordPress 3.1 install, save for this one edit, and all my plugins function correctly, Custom Permalinks works perfectly.
While I wouldn’t suggest just splicing code for every upgrade (obviously, eventually, it’ll cause more problems), maybe someone with more programming experience than me can look at the differences in the code in that section to see precisely what changed, and why it could have caused conflicts. I’m posting this because it gave me fits trying to fix the conflict and none of the other suggestions worked, but this code tweak did.
If this doesn’t solve your category/tag link list 404’s (pulldown and top level menus) when you have a custom permalink for Blog Posts, try this “action” function. It’s worked on every site I’ve tried (including multi-sites) WITHOUT having to tinker with .htaccess, change the existing permalink structure, or disable any installed plugins.
The problem is with 3.1’s canonical redirect. Sometimes, just disabling the redirect fixes the pblm. But, if this doesn’t solve it for you, here’s a more extensive alternative hotfix link. Just put the code in your theme’s functions.php file.
http://wpcodesnippets.info/blog/how-to-fix-the-wp-3-1-custom-permalinks-bug.html
