Your plugin seems to faithfully create 2 (or more) rewrite rules per category which results into a large number of rewrite rules. I have created over 600 categories, and have selected 'remove the "category" slug.' Also, I'm not using any tags.
With DEBUG turned on I get this error, which seems to be a massive list of rewrite rules that exceeds a mysql limit???
WordPress database error: [Cannot put record into object 19 because
its size 194481 is greater than 131036.]
With debug turned off, your plugin/rewrites seem to work OK until I moved server into production. With a large number of rewrite hits I got this in my error.log. which brings down WordPress (or slows everything down to a crawl).
[Wed Nov 14 18:48:58 2012] [error] [client] PHP Catchable fatal error: Object of class WP_Error could not be converted to string in .../wp-content/plugins/wordpress-seo/frontend/class-frontend.php on line 705