Strong singly ionized magnesium (Mg II) absorption lines in quasar spectra typically serve as a proxy for intervening galaxies along the line of sight. Previous studies have found a correlation between the number of these Mg II absorbers and the Faraday rotation measure (RM) at ~5 GHz. We cross-match a sample of 35752 optically identified non-intrinsic Mg II absorption systems with 25649 polarized background radio sources for which we have measurements of both the spectral index and RM at 1.4 GHz. We use the spectral index to split the resulting sample of 599 sources into flat-spectrum and steep-spectrum subsamples. We find that our flat-spectrum sample shows significant (~3.5{sigma}) evidence for a correlation between Mg II absorption and RM at 1.4 GHz, while our steep-spectrum sample shows no such correlation. We argue that such an effect cannot be explained by either luminosity or other observational effects, by evolution in another confounding variable, by wavelength-dependent polarization structure in an active galactic nucleus, by the Galactic foreground, by cosmological expansion, or by partial coverage models. We conclude that our data are most consistent with intervenors directly contributing to the Faraday rotation along the line of sight, and that the intervening systems must therefore have coherent magnetic fields of substantial strength (B{bar}=1.8+/-0.4{mu}G). Nevertheless, the weak nature of the correlation will require future high-resolution and broadband radio observations in order to place it on a much firmer statistical footing.