How do I find the average kinetic energy of atoms or molecules that exist as a solid? I know that for gases I can use 'Kinetic Theory' to relate the average velocity of a gas molecule to the temperature of the gas, but how can I find the average vibrational velocity of a molecule (that exists as a solid) as a function of the solid's temperature? 
Intuitively I'm pretty sure at a certain temperature, the average velocity for gas molecules will be much higher than the average velocity for solid molecules. If I had to find a physical reason for this, I would probably say that as a solid some of the 'thermal energy' exists as potential energy bonds between the molecules, and so not that much exists as kinetic energy. If that's the case, can I do something like:
$$K_s = K_g - E_b$$
where $K_s$ is the average kinetic energy of a solid molecule, $K_g$ is the average kinetic energy of a gas molecule at the same temperature, and $E_b$ is the energy 'stored' in the inter molecular bonds between the molecules of the solid?
 A: The main difference between gases and solids is indeed that in the latter, interactions between constituents are not negligible.
However, i do not think that your approach is valid, because the right result should be (using your notations) $K_s = K_g$.
Here is an approximate explanation :
The situation of a solid can be modelled this way : the interaction between two particles of this solid is described by a potential $U$ that is a function of their relative position. For reasonably low temperatures, the particles will remain close to their equilibrium position and oscillate thermally around it.
For small deviations around this position, the position can be approximated to be $$U(\vec{x}) \simeq \frac{1}{2} k \vec{x}^2$$
Where $x$ is the deviation of a particle from its equilibrium position.
For oscillators, the energy is equally distributed between potential and kinetic energy so that :
$$\frac{1}{2}m\langle \vec{v}^2 \rangle = \frac{1}{2}k \langle \vec{x}^2\rangle$$
As stated by the equipartition theorem, to each degree of freedom of the system corresponds an average energy $\frac{1}{2} k_B T$. So, just like in gases, the average kinetic energy is still given by :
 $$\frac{1}{2}m\langle \vec{v}^2 \rangle = \frac{3}{2} k_B T$$
What really differs is that when interactions aren't negligible anymore, the total energy is the sum of the kinetic energy and the potential energy which is on average (using the two previous equations) $$\frac{3}{2} k_B T + \frac{3}{2} k_B T = 3 k_B T$$
This might sound surprising that molecules can go as fast in a solid as in a gas, but note that in a solid they don't go further than $\langle \vec{x} \rangle$ on average and their high kinetic energy is due to their oscillation frequency $\omega = \sqrt{\frac{k}{m}}$.
Side note
Since the average thermal energy for one particle of the solid is $3k_B T$, the average energy for $N$ solids is $3Nk_B$. As a result the heat capacity of a solid in $J/K/mol$ should approximately be around $3R$, and this result, known as the Dulong–Petit Law, has some experimental support, giving some credit to this approach.
