First of all, thank you for report the issue.
I think I fixed that issue in this commit: FIX: correct notification when tag or category is added (#8801) · discourse/discourse@20e7fb1 · GitHub
Basically, I improved a little bit the logic around notification
If the user has already seen the post, the type of notification should be edited. The case for that is when for example OP will add category or tag which is watched by another user.
However, when the user hasn’t yet seen the post, the type of notification should be “new
reply”. The case for that is when for example topic is under private
category and set for publishing later. In that case, we modify an
existing topic, however, from the user perspective, it is like a new post.
Could you confirm if that is solving the mentioned issue?