I'm using v.7 of the plugin with this theme.
Even when no other plugins are active, when i click either of my category pages i get a 404 File Not Found error.
As soon as i deactivate WP NCB plugin, the page works fine - with the category base back in there. I'm not sure what else to try as this a basic attempt at using this plugin. For SEO purposes, i don't even want to use WP for my new site without relying on this plugin.
I've tried lots of different permalink settings as well.