I also tried to add a "test" category and if I add the test for all the three languages I'm trying to have in the end IT WORKS.
So, the living shop categories with default language can't be updated to have other languages but new categories can have all the three and they appear on the site as well.
How would I get all the default language old categories in other languages without the category tree error and saving the info of category names, descriptions, product names and descriptions for the other languages as well?
There must be some bug here since I remember doing this before with another shop as well. So if I would put all desired languages as once to the shop it would work but if I go online with one language only and want to add others later, it seems too complicated to do and you get this category tree error and not saving information for the categories and products.