This thread is resolved. Here is a description of the problem and solution.
Problem: WPML 3.9 had brought an issue with Custom Post Types (or Products) returning a page not found -> error (404).
Solution: This issue is fixed already with WPML 3.9.1 so if you have this issue please update to WPML 3.9.1 (you should see an update message in your plugins page)
Then please go to Settings -> Permalinks and click Save Changes without making any changes.
Relevant Documentation: https://wpml.org/faq/install-wpml/
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.