Same thing was happening to one of my 3.7.1 sites.
'hierarchical' => false
was the fix after resaving my permalink structure.
I was looking for this issue under just 404 permalink custom post type and it didn’t come up. However once I added 3.7.1 then I saw others with issues.
Thank you for helping us solve this bug.