We investigate the relationship between the linewidths of broad Mg II lambda2800 and Hbeta in active galactic nuclei (AGNs) to refine them as tools to estimate black hole (BH) masses. We perform a detailed spectral analysis of a large sample of AGNs at intermediate redshifts selected from the Sloan Digital Sky Survey, along with a smaller sample of archival ultraviolet spectra for nearby sources monitored with reverberation mapping. Careful attention is devoted to accurate spectral decomposition, especially in the treatment of narrow-line blending and Fe II contamination. We show that, contrary to popular belief, the velocity width of Mg II tends to be smaller than that of Hbeta, suggesting that the two species are not cospatial in the broad-line region. Using these findings and recently updated BH mass measurements from reverberation mapping, we present a new calibration of the empirical prescriptions for estimating virial BH masses for AGNs using the broad Mg II and Hbeta lines. We show that the BH masses derived from our new formalisms show subtle but important differences compared to some of the mass estimators currently used in the literature.