We present the results of a search for unusually rapidly rotating giant stars in a large sample of K giants (~1300 stars) that had been spectroscopically monitored as potential targets for the Space Interferometry Mission's Astrometric Grid. The stars in this catalog are much fainter and typically more metal-poor than those of other catalogs of red giant star rotational velocities, but the spectra generally only have signal-to-noise ratio (S/N) of ~20-60, making the measurement of the widths of individual lines difficult. To compensate for this, we have developed a cross-correlation method to derive rotational velocities in moderate S/N echelle spectra to efficiently probe this sample for rapid rotator candidates. We have discovered 28 new red giant rapid rotators as well as one extreme rapid rotator with a vsin i of 86.4km/s. Rapid rotators comprise 2.2% of our sample, which is consistent with other surveys of brighter, more metal-rich K giant stars. Although we find that the temperature distribution of rapid rotators is similar to that of the slow rotators, this may not be the case with the distributions of surface gravity and metallicity. The rapid rotators show a slight overabundance of low-gravity stars and as a group are significantly more metal-poor than the slow rotators, which may indicate that the rotators are tidally locked binaries.