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.