For the SEO part you might get better answers on the Pro Webmasters Stack Exchange. I will focus on the performance.
From your example I assume your permalink structure was %category%/%postname%/. Because of the way WordPress parses the incoming URL, this will result in verbose page rules, which means that each page (not post) you create gets their own set of rewrite rules. If you don’t have many pages this does not matter much, if you have a lot of pages (say, above 50), this can be a serious performance hit or even stop your site from working.
You use the Custom Permalinks plugin, but a quick look at the code makes me doubt it will scale well when you have a lot of posts. I’m not a MySQL expert, but I think the database can’t use an index effectively to speed up that query it does at every URL request.
If you want to use the same structure for every post (%custom-taxonomy%/%postname%/), I suggest you modify the rewrite rules to match this. I believe you can even do this by setting the permalink structure to %category%/%postname%/ and filtering the post_rewrite_rules by replacing category with your custom taxonomy slug.
But if you don’t use categories, wouldn’t it be easier to re-use this taxonomy so it fits your needs? You can change the labels of the default taxonomies so they look like your custom taxonomies. The benefit is that categories have very strong support everywhere in WordPress, while the custom taxonomies are still new and can’t always do everything (as easy) as categories can.