We present accurate metallicity measurements for 121 damped Lya systems at 0.5<z<5 including ~50 new measurements from our recently published Echellette Spectrograph and Imager surveys. This dataset is analysed to determine the age-metallicity relation of neutral gas in the universe. Contrary to previous datasets this sample shows statistically significant evolution in the mean metallicity. The best linear fit rate to metallicity vs. redshift is -0.26 +/- 0.07 dex corresponding to approximately a factor of 2 every Gyr at z=3. The DLA continue to maintain a floor in metallicity of ~1/700 solar independent of observational effects. This metallicity threshold limits the prevalence of primordial gas in high redshift galaxies and stresses the correspondence between damped systems and star formation (i.e. galaxy formation). This floor is significantly offset from the metallicity of the Lya forest and therefore we consider it to be more related to active star formation within these galaxies than scenarios of enrichment in the very early universe. Finally, we comment on an apparent missing metals problem: the mean metallicity of the damped systems is ~10x lower than the value expected from their observed star formation history. This problem is evident in current theoretical treatments of chemical evolution and galaxy formation; it may indicate a serious flaw in our understanding of the interplay between star formation and metal production.