I am having a similar problem to http://wordpress.org/support/topic/custom-post-types-permalinks-404
I have a custom post type called "video." All was working fine with my custom post rewrites when I had it like this:
In my theme's functions.php register_post_type arguments I just had:
'rewrite' => true,
and in my permalinks I had it set up as /0/%postname%/
Everything was working fine with regular posts coming out like: sitename.com/0/post-name
and videos coming out like sitename.com/0/video/post-name
I was given a request by my supervisor to remove the "/0/" and the "/video/" from all URL's so what I did was go back into my themes functions.php and replaced
'rewrite' => true, with
'rewrite' => array( 'slug' => '', 'with_front' => true),
and then in my permalinks I replaced "/0/%postname%/" with just "/%postname%/".
Now the regular posts are coming out as desired but the custom posts (videos) are all coming up 404.
---------------------------------------
One other thing: If I just set the default in the permalink structure, the videos show up fine as:
sitename.com/?video=post-name
---------------------------------------
Here's something else -
If I change
'rewrite' => array( 'slug' => '', 'with_front' => true), to
'rewrite' => array( 'slug' => '', 'with_front' => false),
and then in my permalinks I replaced "/%postname%/" with "/blog/%postname%/"
Then the custom video posts show up
as sitename.com/post-name (as desired)
but the regular posts then become 404.
Any thoughts out there on this puzzle?