So I have been running into a particularly pain in the ass problem since the 3.1 upgrade for WordPress. I thought others out there might be having the same issue. It is a rather simple but very important thing for all websites, and that is the permalink settings.
Since the drop and me upgrading to 3.1 on my sites I have been seeing the permalinks break when using anything but the default setting. I tend to use a custom setting of /%postname%/ and it has always worked for me fine until the recent update.
Well what I found was needed was to make a simple change the custom setting in the following manner /index.php/%postname%/ this has solved the issue for me on a few sites. Now there is also a couple sites it has not solved the issue and what I found there was a plugin I really like is no longer playing nice.
The plugin in question is Multi-page Toolkit found here plugin site you will have to disable the plugin until there is either an update or WordPress fixes whatever it is that they changed causing issues.