There seems to be a conflict between w3tc and wpml. When both plugins are enabled, modifying permalinks is not possible any more. When disabling either w3tc or wpml permalinks can be modified. It is not clear which plugin causes this issue...
As mentioned here:
WPML Multilingual CMS – Installed version (2.5.2)
WPML String Translation – Installed version (1.4.0)
Yoast WPSEO 1.2.5