We report new spectral types or spectral classification constraints for over 600 stars in the Orion Nebula Cluster (ONC) based on medium resolution (R ≈ 1500-2000) red optical spectra acquired using the Palomar 200'' and Kitt Peak 3.5 m telescopes. Spectral types were initially estimated for F, G, and early K stars from atomic line indices while for late K and M stars, which constitute the majority of our sample, indices involving TiO and VO bands were used. To ensure proper classification, particularly for reddened, veiled, or nebula-contaminated stars, all spectra were then visually examined for type verification or refinement. We provide an updated spectral type table that supersedes previous work, increasing the percentage of optically visible ONC stars with spectral type information from 68% to 90%. However, for many objects, repeated observations have failed to yield spectral types primarily due to the challenges of adequate sky subtraction against a bright and spatially variable nebular background. The scatter between our new and our previously determined spectral types is approximately two spectral sub-classes. We also compare our grating spectroscopy results with classification based on narrow-band TiO filter photometry, finding similar scatter. While the challenges of working in the ONC may explain much of the spread, we highlight several stars showing significant and unexplained bona fide spectral variations in observations taken several years apart; these and similar cases could be due to a combination of accretion and extinction changes. Finally, nearly 20% of ONC stars exhibit obvious Ca II triplet emission indicative of strong accretion.