While studying thermal physics at school, I have been taught that solids simply have more potential energy than the liquids and gases. Note that it was said that this potential energy is due to the intermolecular bonds between the atoms. However, my intuition makes me doubt this, why would there be more potential energy in a solid??? Lets see: the internal energy is the sum of the kinetic and potential energies of a body. Well liquids and gases have more kinetic - pretty clear. As for, our original point, the potential: well, if the body has potential to do work, via lets say, chemical reactions, then its solid form will have a higher activation energy, as the intermolecular bonds have to be broken first - so the energy then released from combustion or what not, is less than that of its gaseous equivalent! Then how is it, that solids are somehow said to have more "potential" energy than the more energetic states. I, upon questioning this, have been told that this is due to the forces of the molecular bonds, but really I think, these forces signalize a lack of potential energy!
Combustion is a chemical reaction where the molecules rearrange themselves and is VERY VERY different from change of phase. The energy stored in the solid phase is not necessarily more than that stored in the liquid phase. For example, it takes more energy to convert water into stream ($2260 KJ/kg$) than ice into water ($334 KJ/Kg$).
Since you're talking about thermal physics, it's probably worth talking about this purely in a thermal context.
What does it mean for something to have a high amount of energy? It means that we can do a lot of work with it. So let's say we have some sort of machine that uses something to do work as efficiently as possible. Since we're talking about solids and liquids and gases in the abstract, we can assume that we're not extracting any kinetic or potential energy (since that's dependent on the exact context of the solid). Our machine, then, is a heat engine. We do work by pulling heat from a hot object and dumping it into a cold object. This means, then, that we can extract more heat from a hotter object, so hotter objects have more energy. Which is (generally) hotter: a solid or a gas?
In short, your teacher is wrong.