You can't select an item type as a criterion for a collection if it is not selected to be included in search results. In the "Search settings" (/@@search-controlpanel) you can exclude certain content types from being "searched and be available in the user facing part of the site". That actually corresponds to the list of types_not_searched in site_properties. Now that list is excluded from available content types as a criterion for collections. At least for the UI–it still works.
If you want a content type to not show up in search results but in collections, you can work around that problem by enabling the type for search temporarily, set up your collection and disable the type for search afterwards. It's a bit odd, because you can't even see your selection in the criterion page afterwards but it works.
I'd say this is a bug and the collection UI should present all available types in the option box, if searchable or not. I guess I should file a report.
Update: I submitted a bug report.