I came across a nightmare of a problem today. Everytime I viewed my custom post types I kept getting a 404 error. I just couldnt understand what was going on. Thanks to this article I finally solved the problem.
When setting up custom post types and a custom permalink structure add the below code to the function used to create custom posts.
flush_rewrite_rules( false );
I just wanted to write a quick post to highlight the problem but an explanation of why this is needed can be found on the wordpress codex.