Oh well, in the end I have used something similiar:
$catcount = substr(@$navlink['note'], 1); //remove first character or bracket
$catcount = substr($catcount, 0, -1); //remove last character or bracket
This removed the brackets.
That code has to be placed just after the else statement in function nav_link in the advanced theme.