Maybe they just meant you can't get more notoriety for that same thing. In other words, you can't get another point of Notoriety for having already killed that Johnson.
Not the best example, but maybe use "dealing with a dragon" instead. If you make a deal with Lofwyr, you get Notoriety. If you continue to deal with Lofwyr, it doesn't result in more Notoriety. However, if you start dealing with Celedyr too, that's worth more Notoriety.
So I guess if we go back to the first example, if you kill a Johnson, you get Notoriety. If he somehow miraculously comes back from the dead, and you kill him again, not worth any more Notoriety. People already know you killed him, they aren't surprised when you do it again. Go off and kill another Johnson? worth more Notoriety.
To answer the original question, however. I think it is just "having the negative quality" that results in a point of Notoriety. The system never mentions that the scale of the quality affects how much notoriety you get, and even when the various qualities have different values (karma- and effect-wise) they are all still worth just 1 notoriety (with the exception of Bad Rep, whose effect is specifically +3 Notoriety).
It doesn't matter how bad your gremlins are, word gets out that you are a jinx so you get notoriety.