Why does Einstein's theory of specific heat fail only at one extreme of temperature?

The question starts from an incorrect statement. Einstein's theory, but also Debye's theory do not work well at high temperature 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 negligeable, but the harmonic approximation is still accurate. By increasing further the temperature, soon or later departures from harmonic approximations become evident (due to anharmonic effets and creation of defects) and Dulong and Petit 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 the way 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 which 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.