Do you have any Pages with the same slug as the post type key? There appears to be a WordPress bug with this. From the Easy Post Type FAQs:
I get a 404 page when trying to view a post of my custom post type
This can be caused by having a page with the same slug as your custom post type key. The Page does not need to be published (it can even be in the trash) for this issue to exists.
You will either need to permanently delete the Page or create the a new post type with a different key.
This is an issue with WordPress rewrite. We are looking into how to workaround the issue.