Replace and Association

Associations are funny beasts -- neither fish nor fowl. Sometimes they are treated as atomic expressions and sometime they are not. For pattern matching purposes their atomic nature seems to rule. Consider this far more elementary case.

a = <|"a" -> 2|>;
AtomQ @ a

True

Any expression can be used as a pattern and always matches itself.

MatchQ[a, <|"a" -> 2|>]

True

But other than this trivial case, no pattern based the form of a matches a. All of

MatchQ[a, <|_ -> 2|>]
MatchQ[a, <|"a" -> _|>]
MatchQ[a, <|_ -> _|>]
MatchQ[a, <|_|>]

give False. This is the behavior to be expected of atoms, so to modify an association with ReplaceAll, it looks like you are going to have use Normal.

Association[Normal[a] /. "a" -> "b"]

<|"b" -> 2|>

As of 10.4, there is now KeyValuePattern:

{<|8 -> 7|>, <|"a" -> "red", 6 -> 3|>} /. KeyValuePattern["a" -> "red"] :> Nothing

returns

{<|8 -> 7|>}

(The code reads a little weirdly - going by names alone, an Association shouldn't match a KeyValuePattern in my mind, because an Association isn't a key/value pair - but the intention is clear.)