If it is an issue with custom post types then I've seen this issue a couple of times and it always seemed to lead to the external plugin that creates the post types and taxonomies. Currently, I'm using 'GD Custom Posts And Taxonomies Tools', and for some reason, you can have a created taxonomies hold which post types you want it in, but the post types won't add it unless is modified as well. I've also seen the external plugin bug up by adding empty values for post types and taxonomies.
Idk which custom post and taxonomies tools your using, but I would recommend double checking both the post types and taxonomy settings. They also need to be set to public and query-able.