Custom Post Types not working with pretty urls enabled

Hi.
I’m using a plugin that has custom post types and so far it look ok unless the permalink structure is anything but the default. If it’s the default I can view the custom post, but if not, all i get is a 404 error.

Is this a bug or something wrong with my plugin?

Thank you.