Ok, I've found the workaround thought it fixes the problem temporarly.
Basically when a category is created, depending on the languages that you have installed on it will create as many entries in the ps_category_lang table as languages you have, meaning that you will be able to open any category from store A on store B or vice versa.
To temporarly fix it, just made a query to delete the entries on category_lang that don't belong to the shop in question.
(dont forget to back up)
KR,