There was a change recently to not include tags from permission controlled categories by default in case the number could be sensitive in nature. But there is an admin setting, include secure categories in tag counts, that you can use to go back to the old behaviour. 
I think when you reverted the permissions to see if that was the cause you needed to wait for the background job to recalculate the numbers, which is why you didn’t immediately see a change.