If you re-create the definition, then WP should find them all again. There's nothing magic about that process, you just need to ensure that you use the *exact* same name in the definition. READ: each post in the WordPress database is already "associated" with its post_type via the "post_type" column. You cannot easily "disassociate" it. The post_type is inherent in the post, it is not defined via any association or relationship.
A good cross-check would be to view your wp_posts table and check the "post_type" column for the exact name used and make sure you use that identical name when you re-create the definition. See the bit here about "Ghost Posts": https://code.google.com/p/wordpress-custom-content-type-manager/wiki/DeletePostType
I always export a backup copy of the CCTM content-type definition because sometimes site users have zero idea of what they're doing and end up deleting something vital. See https://code.google.com/p/wordpress-custom-content-type-manager/wiki/Export