We present rest-frame optical spectra from Keck/MOSFIRE and Keck/NIRES of 16 candidate ultramassive galaxies targeted as part of the Massive Ancient Galaxies at z > 3 Near-Infrared Survey (MAGAZ3NE). These candidates were selected to have photometric redshifts 3 less than or similar to z (phot) <4, photometric stellar masses log(M-& lowast;/M-circle dot) > 11.7, and well-sampled photometric spectral energy distributions (SEDs) from the UltraVISTA and VIDEO surveys. In contrast to previous spectroscopic observations of blue star-forming and poststarburst ultramassive galaxies, candidates in this sample have very red SEDs implying significant dust attenuation, old stellar ages, and/or active galactic nuclei (AGN). Of these galaxies, eight are revealed to be heavily dust-obscured 2.0 < z < 2.7 galaxies with strong emission lines, some showing broad features indicative of AGN, three are Type I AGN hosts at z > 3, one is a z similar to 1.2 dusty galaxy, and four galaxies do not have a confirmed spectroscopic redshift. In fact, none of the sample has divided by z (spec) - z (phot)divided by < 0.5, suggesting difficulties for photometric redshift programs in fitting similarly red SEDs. The prevalence of these red interloper galaxies suggests that the number densities of high-mass galaxies are overestimated at z greater than or similar to 3 in large photometric surveys, helping to resolve the "impossibly early galaxy problem" and leading to much better agreement with cosmological galaxy simulations. A more complete spectroscopic survey of ultramassive galaxies is required to pin down the uncertainties on their number densities in the early Universe.