2017-07-24 WPML no longer supported.
In order to get WPML and Perfect SEO Url work properly you will need to install WPML String Translation. Go to WP Admin > WPML > String Translation. Find string product-category. Set all translations of the string product-category to product-category. Find string product. Set all translations of the string product to product or product/%product_cat%.