I'm unsure of what version of wordpress seo this actually started, but I have the latest 1.4.24 on all the sites now and just noticed this. When I turn the plugin on and off on any of them, the category pages 404 on some sites and some they show the home page content and not the category. To be sure it wasn't caused by another plugin or the theme, I confirmed it on a fresh new site using the twentythirteen theme and no other plugins.
The problem is easily fixed by resaving the permalinks in the wp-admin, but I think this could become very frustrating. It's often that people have to turn off and on their plugins to check for conflicts etc - but they'll not always remember to go resave the permalinks right away.
We use the file monitor plugin on all the sites also and it reports a change to the htaccess file after upgrades and turning on or off the wordpress seo plugin. (Viewing the htaccess shows that nothing has actually been changed in it though.)
I found a few somewhat similar support posts, but at the end of this one: http://wordpress.org/support/topic/plugin-wordpress-seo-by-yoast-category-and-tags-dont-work-anymore/page/3?replies=78 the last post asks to make a new support thread if experiencing the issue.