If temperature is average KE per particle, and heat is total KE of all the particles, how can molar heat capacity vary? If temperature is defined as the average kinetic energy per particle, and heat energy is defined as the total kinetic energy of all the particles (or more strictly, heat transferred is the total kinetic energy transferred to those particles), surely we can get heat by just multiplying temperature by the number of particles? If so, shouldn't molar heat capacity be constant across all substances?
I'm fairly sure I'm missing something that should be obvious here...
 A: If equipartition holds, temperature corresponds to average energy per degree of freedom, which - besides kinetic ones - include internal ones like vibrational and rotational degrees of freedom.
Even in cases of structurally similar molecules with the same degrees of freedom, because of energy quantization (in particular vibrational energy), heat capacity may still differ - see eg the heat capacity of diatomic gases.
A: 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.
