This problem affects all of my seperate WP sites. I have not changed anything on my LAMP server which is running all the latest php, apache, and mysql versions.
I started getting a bunch of 404 errors in Goggle webmaster tools and though I would investigate. Turns out WordPress has now re-written my category and tag base's to reflect my custom permalink structure.
My custom permalink structure: /archive/%postname%/
Example original: mysite.com/tag/example-tag
Example after upgrade: mysite.com/archive/tag/example-tag
To resolve my problem (as long as WordPress doesn't magically change back one day) i simple added this to all of my sites .htaccess files.
Redirect 301 /tag /archive/tag Redirect 301 /category /archive/category
Anyone else see this after updating?
I just verified that the problem is with the change from 3.1 to 3.1.1 I had a blog that I neglected to update so I just did that a second ago and the permalink structure changes exactly as I described above.