It sounds like you’re using “pretty permalinks” with %postname%. If so, you need to make sure that you don’t have page names that match your post type names. WordPress can only allow a particular slug to resolve to one page (that’s why you can only get one or the other to work at a time). Or if you do have matching names, make sure when you register your post types that has_archive is set to false (disallows post type archives) or is set to a different slug (to avoid conflicts). Also, check your rewrite rules when registering your post types. For example, you might have something like:
'rewrite' => array( 'slug' => 'news', 'with_front' => false ),
which means that your “news” post type will be first up in the permalink structure, whereas with_front set to true would prepend your existing permalink structure to the “news” slug. Read more about all this here.
The other possibility (without knowing more about your situation) is that you’ve recently moved your site. In which case you might need to “relocate” your site. See here.
Hope something there is helpful. I know how frustrating those 404’s can be…