This thread is resolved. Here is a description of the problem and solution.
Problem: Slug for a custom post type is translated, however in the front-end the links are still leading to the other (non translated) slug / or the page produces error 404.
Solution: It is always a good idea, first to delete the old slug from WPML -> String Translation. Then you can always go to WPML -> Translation Management -> Multilingual Content Setup -> Custom Posts - and re-translate your slug for the custom post type that you want to have translated.
This is the technical support forum for WPML - the multilingual WordPress plugin.
Everyone can read, but only WPML clients can post here. WPML team is replying on the forum 6 days per week, 22 hours per day.