This sounds more like a theme issue to me. The redirection seems to be correct after typing in the “plages 2”, I'm redirected here: http://www.playas-valencia.com/fr/?s=plages%202
After a few try I got a fatal error which states the following to me:
Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 6 bytes) in /home/content/p3pnexwpnas07_data01/81/2662781/html/wp-content/plugins/sitepress-multilingual-cms/sitepress.class.php on line 5061
This means there is not enough memory left for WPML do do something, that is not disclosed in the error message exactly. The cause might not be WPML, but I'm definitely sure it hsould not run out of memory ever.
You can try increasing your memory limit, that usually helps. You can try higher values like 256M or even 512M if the values in the article are not enough.Best,
If you like my products, don't forget to rate them on codecanyon :)