Why does Einstein's theory of specific heat fail only at one extreme of temperature? Why does Einstein's theory of specific heat of solids work well at high temperatures but fail at low temperatures?
 A: The question starts from an incorrect statement. Einstein's and Debye's theories do not work well at high temperatures whatever high the temperature is.
The correct statement is that Einstein's law fails to account for the low-temperature behavior of specific heat of solids, even qualitatively, but at high temperature, it goes to the Dulong and Petit law limit, which is an accurate description of the specific heat of a solid when quantum effects are negligible, but the harmonic approximation is still accurate. By increasing the temperature further, sooner or later departures from harmonic approximations become evident (due to anharmonic effects and creation of defects), and Dulong and Petit's law does not provide a quantitative description of specific heat, even before the dramatic change of behavior observed at the melting transition.
After this clarification, why Einstein's theory fails qualitatively at low temperatures, giving an exponentially vanishing specific heat instead of the observed $T^3$ behavior?
The reason can be traced back to how the energy density of states behaves in Einstein's model vs. what happens in real systems. In Einstein's model of independent oscillators, all the oscillators have the same frequency $\omega$. Therefore, even a collection of oscillators cannot have energy states between $0$ and $\hbar \omega$. It is the presence of such a gap that accounts for the exponential behavior.
In real solids, the atomic dynamics is controlled by collective normal modes of oscillations. Some of them, the so-called acoustic modes, go to zero linearly, eliminating the gap. In the usual harmonic model, the three-dimensional acoustic modes give rise to the $T^3$ behavior.
