I use a custom structure of /blog/%postname%/ for regular post permalinks (not categories).
After upgrading 3.1.2, I noticed this:
If there's no category base set in the Permalinks settings page - my usual setting - category links are automatically given /blog/category/ as a base:
If I set 'category' as a base, links are correctly set as:
So it seems that in 3.1.2, no category base means either that 'blog' gets assigned as default OR that the category base is using the custom structure I assigned for posts. Either way, there seems to be a new bug here.
Anyone else seeing this?