Mixtures of granular media often exhibit size segregation along the axis of a partially filled; horizontal; rotating cylinder. Previous experiments have observed axial bands of segregation that grow from concentration fluctuations and merge in a manner analogous to spinodal decomposition. We have observed that a new dynamical state precedes this effect in certain mixtures: bidirectional traveling waves. By preparing initial conditions; we found that the wave speed decreased with wavelength. Such waves appear to be inconsistent with simple partial differential equation models which are first order in time.