Temperature is not the average kinetic energy of a particle it is the average energy per mode.1
In very simple models (i.e. the monoatomic ideal gas) the number of modes per particle is fixed and can not vary, so that the heat capacity of these simple models is indeed fixed. And in fact, good approximations to mono-atomic, ideal gases (noble gases, other simple gases at low temperature but still low pressure) do all have nearly the same heat capacity.
More complicated real systems however have more modes. Depending on the system and the temperature molecular rotational and vibration modes may be present. At still higher temperature molecular and atomic excitation modes come into play. In crystal system phonon excitations are available.
So of these modes are only available when the temperature gets high enough, and an interesting thing to do is observer the heat capacity of a gas go through step-like increases as new modes become occupied.
This looks roughly like
(figure converted from the Wikipedia image at http://en.wikipedia.org/wiki/File:DiatomicSpecHeat1.png). The steps represent temperature where the mean energy per mode increases to the ground state energy of the newly accessible mode. They are not sharp because the actually energy in any particular microscopic mode is not guaranteed to be exactly the mean energy per mode, but could be a little more or a little less.
1 What is a mode? I'm glad you asked...
Without being too precises a mode is any distinct way for energy to be stored in microscopic physics inside a bulk material. That is the all the ways there can be "internal energy". For instance the translational motion of particles in a mono-atomic gas is three modes ($mv_x^2/2$, $mv_y^2/2$ and $mv_z^2/2$; and we distinguish them because we do study one and two dimensional systems and it matters). More complicated molecules can also rotate (a $I\omega^2/2$ contribution for every direction it can rotate) or vibrate ($kx_{max}^2/2$ for each vibration) and so on.