What you've heard is correct. If you have developed specialized views of your custom post type (archive pages, single pages, categories, or setup custom queries for your post type ) and a user changes themes all those views are lost.
It's true, as has been mentioned, that the Custom Post Type should be created in a plugin, but the presentation of that cpt is created in the theme.
The real question, is once you've put time and energy into a creating a look and feel of your site, why would you let a user change the theme? You have created a design: stay with it. The reality is that more than just the custom post presentation will be lost if you change themes. The presentation of your blog goes too. Your colors, your fonts, your layout all are gone and back to what ever the new themes settings are.
Now when the theme is changed, your pages, posts, AND cpt will still be displayed (because you created the CPT in a plugin) but they will be presented in a fashion that the new theme designer created. Since that designer was not thinking about your cpt wordpress will just treat your posts as default blog posts.
Think about it though, if you give a user the ability to change themes, then they likely can change your plugins too.
TLDR: Choose a theme and stick with it(don't change it unless there is a good reason). Create your CPT. Do it in a plugin.