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: bi-directional traveling waves. By preparing initial conditions, we found that the wave speed decreased with wavelength. Such waves appear to be inconsistent with simple PDE models which are first order in time.