I had this same issue. I have found that installing Qtranslate Slug plugin (https://www.ads-software.com/plugins/qtranslate-slug/) fixed it and all the links where appearing again. After installing the Qtranslate Slug plugin go to the categories and add the slugs again. Hope this helps.
