Global Site Search breaks permalinks if category is used in permalink structure (3.1)

Hi there, I have been trying to track down a problem with my permalinks since updating WP. The problem occurs when Global Site Search (GSS) is active, and goes away when it is inactive.

My preferred permalink structure is: /%year%/%category%/%postname%/

When I use this permalink structure and GSS is active the following happens:
1. Home page displays fine - listing recent posts as usual.
2. Clicking any post delivers a 404 not found error.

If I disable GSS, everything works.
If I re-enable GSS, and remove %category% from my permalinks, everything works.

GSS is doing something that conflicts with standard rewrite rules.

I don't want to drop %category% from my permalinks because it will break any incoming links, and probably have big SEO implications. But I also want global site search to work.

[aside]
Sorry about duplicate post. The is a problem with the forum. My first version had '%category%' in the title which was not handled correctly, making that post innaccessible. I suggest a moderator remove it. Also mention in the appropriate ear that forum title sanitization has a minor bug.
Kind regards,
Kevin