Commissioning observations with the Apache Point Observatory Galactic Evolution Experiment (APOGEE), part of the Sloan Digital Sky Survey III, have produced radial velocities (RVs) for ~4700 K/M-giant stars in the Milky Way (MW) bulge. These high-resolution (R ~ 22, 500), high-S/N (>100 per resolution element), near-infrared (NIR; 1.51-1.70 μm) spectra provide accurate RVs (epsilonV ~ 0.2 km s-1) for the sample of stars in 18 Galactic bulge fields spanning -1° -32°. This represents the largest NIR high-resolution spectroscopic sample of giant stars ever assembled in this region of the Galaxy. A cold (σV ~ 30 km s-1), high-velocity peak (V GSR ≈ +200 km s-1) is found to comprise a significant fraction (~10%) of stars in many of these fields. These high RVs have not been detected in previous MW surveys and are not expected for a simple, circularly rotating disk. Preliminary distance estimates rule out an origin from the background Sagittarius tidal stream or a new stream in the MW disk. Comparison to various Galactic models suggests that these high RVs are best explained by stars in orbits of the Galactic bar potential, although some observational features remain unexplained.