First of all, thank you for report the issue.
I think I fixed that issue in this commit: https://github.com/discourse/discourse/commit/20e7fb1c958790fa2dafc80bf6fe76b0556a2b92
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?