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.