We present measurements of the magnetoconductance of long and narrow quasi-one-dimensional gold wires containing magnetic iron impurities in a temperature range extending from 15 mK to 4.2 K. The dephasing rate extracted from the weak antilocalization shows a pronounced plateau in a temperature region of 300-800 mK, associated with the phase breaking due to the Kondo effect. Below the Kondo temperature, the dephasing rate decreases linearly with temperature, in contradiction with standard Fermi-liquid theory. Our data suggest that the formation of a spin glass due to the interactions between the magnetic moments is responsible for the observed anomalous temperature dependence.