WordPress version: 3.4.2
WordPress SEO version: 126.96.36.199
I did this: Updating WordPress from 3.4.1 to 3.4.2 and updating the plugin
After that, the category permalinks in my main menu are like this:
Before updating I had another problem: When I added a new category all categories lead to Page not found. Resolving this I had to deactivate the first item in the WordPress SEO Permalinks options, saving, activating again, saving. Then it worked fine again.
Please help :-)