Custom Post Type in Permalink Structure

I'm looking for the best way to add a taxonomy slug into the permalink structure.

For example, for example, for a "Format" taxonomy with choices Bio, Photos, Videos:

Permalink Structure: /%category%/%format%/%postname%/
Category: John Travolota
Format: Bio
Result: http://example.com/john-travolta/bio/this-is-a-bio-post
Post without a "Format" taxonomy chosen: http://example.com/john-travolta/this-is-a-regular-post

This plugin http://wordpress.org/extend/plugins/post-format-permalink/ seems to target this issue, however any post without a "Format" chosen results in a 404 error.

Thanks in advanced!