Since average KE is literally a definition of temperature [...]
This is not a good definition of temperature. Temperature is often (but not always) a measure of the average energy (in the sense that the relationship between temperature and average energy is one-to-one), but in certain systems the relationship is more complicated.
The proper definition of temperature is
$$\frac{1}{T} = \left(\frac{\partial S}{\partial U}\right)_{V}$$
That is, if you add a small bit of energy to the system then the system's entropy changes because that extra bit of energy can be distributed between the particles in a number of different ways. The ratio of the change in energy to the change in entropy gives the temperature. If a small parcel of energy increases the entropy dramatically, then the temperature is low; if the entropy does change very much at all, then the temperature is high.
As a simple example, consider a 3D Einstein solid. It's not difficult to show that the average internal energy per particle is given by
$$\left<E\right> = \frac{3\hbar\omega}{2}\coth\left(\frac{\hbar\omega}{2kT}\right)$$
This different from what one would naively expect by applying the equipartition theorem to a system of classical oscillators (in which the energy is shared equally between kinetic and potential). In that case, we would simply find that $\left<E\right> = 3kT$.
From these relations we can compute the heat capacities of our systems, $C = \left(\frac{\partial U}{\partial T}\right)_V$ where $U=N\left<E\right>$. We find that for the Einstein solid,
$$C = 3k\left(\frac{\hbar \omega}{2kT}\right)^2 \operatorname{csch}^2\left(\frac{\hbar\omega}{2kT}\right)$$
whereas $C=3k$ for the classical solid.
My intuition says that a higher heat capacity simply tells us some energy is being stored as PE when heat is added.
This intuition isn't bad. Indeed if you restrict your attention to classical physics, you'd be right - the classical counterpart to the Einstein solid has a heat capacity of $3R$ rather than $\frac{3}{2}R$ (note that $R=N_Ak$, where $N_A$ is Avogadro's number) precisely because energy is stored as vibrational potential energy.
It's the quantum effects that are the key here - specifically the fact that the set of allowed energies for each particle is discrete. When the temperature is less than $\hbar\omega$ (which is the spacing between allowed energy levels), there is a dramatic departure from the classical heat capacity of $3k$ because a small parcel of energy changes the temperature quite substantially. If $T/\hbar\omega$ is sufficiently small, then the heat capacity of the Einstein solid can even drop below $3k/2$, the heat capacity of the classical ideal gas.
Diamond is special. The rigidity it gets from its somewhat unique crystal structure makes its effective $\omega$ very large. As a result, its heat capacity is unusually small even for relatively large values of $T$. Here's a plot of its heat capacity compared with aluminum and lead.
