  We present measurements of spin relaxation times (T_1, T_1,rho, T_2) on very
shallow (<5 nm) nitrogen-vacancy (NV) centers in high-purity diamond single
crystals. We find a reduction of spin relaxation times up to 30x compared to
bulk values, indicating the presence of ubiquitous magnetic impurities
associated with the surface. Our measurements yield a density of 0.01-0.1 Bohr
magnetons per nm^2 and a characteristic correlation time of 0.28(3) ns of
surface states, with little variation between samples (implanted, N-doped) and
surface terminations (H, F and O). A low temperature measurement further
confirms that fluctuations are thermally activated. The data support the
atomistic picture where impurities are associated with the top carbon layers,
and not with terminating surface atoms or adsorbate molecules. The low spin
density implies that the presence of a single surface impurity is sufficient to
cause spin relaxation of a shallow NV center.
