[Plugin: Custom Post Permalinks] Adding Post Category to URL Structure results in 404

This seems like it would be a nice solution and very close to solving the issue, though I get a 404 when adding the category into the URL structure such as /%category%/%postname%/
The URL looks perfect though, just no post.

Any thoughts?

thanks!

http://wordpress.org/extend/plugins/custom-post-permalinks/