Hello,
I have the same problem of Udi. In a public main category, I've some public subcategories and some other subcategories with special access. But If I go to the frontend, I see all categories (special and public). I've set with special permission also the items inside the subcategories but it seems not work..
If it can help, this is the page to which I refer:
goo.gl/dYC8Vl