I know I'm just speculating here, but wouldn't the steppe nomadic peoples have simply adopted some other beast of burden? At first, horses weren't developed enough to carry the burden of a grown man. It'd take many a generation before they could transition their forces from chariot-bourne to out-and-out cavalry...