If you have upgraded to WordPress 3.1 recently and are seeing problems with permalinks redirects specially for category pages, you are not alone. There are several people who have reported similar issues and are seeing 500 errors on permalinks and redirects.
There is no straightforward way to fix this issue and it might take a bit of time to figure out what is going wrong. However, some of the core WordPress team members have come up with a plugin that fixes this particular permalink and redirect issues with WordPress 3.1 upgrades.
According to the plugin description, there seems to be a problem with the REQUEST_URI variable being set on certain WordPress 3.1 installations.
This plugin ensures the REQUEST_URI variable is set during the initialization of WordPress, allowing permalinks to work correctly.
So if you are facing the permalink and canonical redirects problem with WordPress 3.1 go ahead and install the Permalink Fix & Disable Canonical Redirects Pack.