Instead of thinking of loose particles in vacuum, better think of small masses attached to their neighbours by little springs, because your matter is cohesive. This model is a first approximation for the molecules in a solid. (This is called the “harmonic oscillator approximation” of a solid.)
The energy is then transported along the medium via the springs.
In fact, you focus too much on kinetic energy alone. A many-particle system with kinetic energy alone would be an ideal gas - and in an ideal gas, sound indeed propagates longitudinally (if at all :-) ).
However, coupled matter has additional potential energy (or exchange energy, interaction energy). The transverse propagation of sound is a permament exchange of kinetic and potential energy. If there's no damping, then in order to oscillate, the particles must have speed zero at the turning points, i.e. zero kinetic energy. Due to conservation of energy, all energy of that particle at its turning point is potential energy. This potential energy might be due to an external field, or due to interaction energy with other particles. It is precisely this mechanism which lets energy propagate in sound.
The question you were asking is very good, indeed, because it is important to understand the exchange of kinetic and potential energy in oscillations, and many people don't understand that (even have no clue about that)...