Permalink settings are at "day and name." I haven't tried the other non-default settings, but I doubt it would make a difference.
Once the plugin is activated, and rewrite rules are flushed, permalinks to custom taxonomies (and almost certainly custom post types) lead to 404 pages. The problem is often corrected by resubmitting the permalink form (not just by visiting the permalink settings page) though I'm not sure exactly why. However, once anything in the system triggers a rewrite rule flush, it reappears.
I took a peak at the wp_rewrite object and found that during problem periods all the rewrite rules for custom posts and taxonomies are missing.
As soon as the plugin is deactivated, everything works fine.
I could reactivate the plugin on our development version of the site, flush the rules, and make it public so you could see, but I don't think you'd get much out of it - just "yep, those custom taxonomy links lead to 404 pages." I'm happy to answer any additional questions you have.