When editing a tab and selecting the category "All Categories" the tab does not appear on any categories. However it does appear if I select a specific category to appear on.
This now works with a new setting that a can be configured per tab, i.e. 'All Categories' which will then mean a tab appears (with the appropriate permissions) under every category. Made it into Beta 2.