  We present a theory of the subgap tails of the density of states in a
diffusive superconductor containing magnetic impurities. We show that the
subgap tails have two contributions: one arising from mesoscopic gap
fluctuations, previously discussed by Lamacraft and Simons, and the other
associated to the long-wave fluctuations of the concentration of magnetic
impurities. We study the latter both in small superconducting grains and in
bulk systems [$d=1,2,3$], and establish the dimensionless parameter that
controls which of the two contributions dominates the subgap tails. We observe
that these contributions are related to each other by dimensional reduction. We
apply the theory to estimate the effects of a weak concentration of magnetic
impurities [$\approx 1 {\rm p.p.m}$] on the phase coherence of Josephson
qubits. We find that at these typical concentrations, magnetic impurities are
relevant for the dephasing in large qubits, designed around a $10 {\rm \mu m}$
scale, where they limit the quality factor to be $Q<10^4-10^5$.
