In Version 11.0.1 (and 10.4.1) the attributes of Association are:
{HoldAllComplete, Protected}
I think the help of AtomQ has a statement:
AtomQ gives True for any object whose subparts cannot be accessed using functions like Map.
notice that it says like Map. For example one can not change the numerator/denominator of fractions or parts of a complex number:
a = 3/4
a /. 4 -> 5
3/4
3/4
a = 1 + 2 I
a /. 2 -> 3
1+2I
1+2I
Or similarly, parts of a sparse-arrays, so that lead me to believe that ReplaceAll does not touch atoms (subatomic parts) in general.
I just found that in the help of ReplaceAll it says, regarding Associations, that:
Most patterns are only compared against the values of an association.
<|a -> f[b -> c]|> /. (k_ -> v_) :> g[k, v]
<|a -> f[g[b, c]]|>
For compound patterns matching an Association, inner patterns match both keys and values:
<|a -> f[b -> c]|> /. _[k_ -> v_] :> g[k, v]
g[a, f[b -> c]]
By excluding heads matching Association, only comparisons against values are done:
<|a -> f[b -> c]|> /. Except[Association][k_ -> v_] :> g[k, v]
<|a -> g[b, c]|>
So apparently Replace can be used with Associations, though I'm not sure where that leaves us, especially the "Most patterns are only compared against the values" is kind of strange; what is meant by most? How can one determine what is checked... so many questions!