We present K-band lambda / DELTA lambda 2600 spectroscopy of five stars (K 14 - 16 mag) within 0.''5 of Sgr A*, the radio source associated with the compact massive object suspected to be a 2.6 x 106 \msun black hole at the center of our Galaxy. High spatial resolution of 0.''09, and good strehl ratios of 0.2 achieved with adaptive optics on the 10-meter Keck telescope make it possible to measure moderate-resolution spectra of these stars individually for the first time. Two stars (S0-17 and S0-18) are identified as late-type stars by the detection of CO bandhead absorption in their spectra. Their absolute K magnitudes and CO bandhead absorption strengths are consistent with early K giants. Three stars (S0-1, S0-2, and S0-16), with r_proj < 0.0075 pc ( 0.''2) from Sgr A*, lack CO bandhead absorption, confirming the results of earlier lower spectral and lower spatial resolution observations that the majority of the stars in the Sgr A* Cluster are early-type stars. The absolute K magnitudes of the early-type stars suggest that they are late O - early B main sequence stars of ages < 20 Myr. The presence of young stars in the Sgr A* Cluster, so close to the central supermassive black hole, poses the intriguing problem of how these stars could have formed, or could have been brought, within its strong tidal field.