Explanation for negative specific heat capacities in stars?

Consider a satellite in orbit about the Earth and moving at some velocity $v$. The orbital velocity is related to the distance from the centre of the Earth, $r$, by:

$$ v = \sqrt{\frac{GM}{r}} $$

If we take energy away from the satellite then it descends into a lower orbit, so $r$ decreases and therefore it's orbital velocity $v$ increases. Likewise if we add energy to the satellite it ascends into a higher orbit and $v$ decreases.

This is the principle behind the negative heat capacity of stars. Replace the satellite by a hydrogen atom, and replace the Earth by a large ball of hydrogen atoms. If you take energy out then the hydrogen atoms descend into lower orbits and their velocity increases. Since we can relate velocity to temperature using the Maxwell-Boltzmann distribution this means that as we take energy out the temperature rises, and therefore the specific heat must be negative.

This is all a bit of a cheat of course, because you are ignoring the potential energy. The total energy of the system decreases as you take energy out, but the decrease is accomplished by decreasing the potential energy and increasing the kinetic energy. The virial theorem tells us that the decrease of the potential energy is twice as big as the increase in the kinetic energy, so the net change is negative.

Although John's answer is quite comprehensive, I would like to add this answer in order to reinforce my qualitative understanding of the matter and to try to provide the OP a more intuitive and qualitative explanation for the negative specific heat capacity as the OP seems to be looking for a more qualitative (and intuitive) sort of explanation.

For usual objects like rocks and stars, the temperature is a direct measure of the internal kinetic energy of the object - i.e., the kinetic energy of its constituents. Now, if - the configuration of such an object be of such a nature that whenever the internal kinetic energy increases (decreases), the structure of the object has to change in a way that makes its potential energy decrease (increase) by an amount greater than the increase (decrease) in its internal kinetic energy - then clearly the specific heat capacity will be negative!

For black holes, the story is a bit different. I haven't studied the work that determines Hawking temperature using the string theoretic microstates of a black hole and thus, I believe I can't really provide an explanatory or a deeper reasoning behind the negative specific heat capacity of black holes - but I will elucidate the mechanism of deriving the specific heat capacity of a black hole and that clearly shows that it must be negative.

The temperature of a black hole is given by $T = \dfrac{\hbar c^3}{8\pi GM}$. The energy of a black hole is to be considered as $E = Mc^2$. Therefore, $dE = -\dfrac{\hbar c^5}{8 \pi G T^2} dT$. Thus, specific heat capacity $C = \dfrac{1}{M}\dfrac{dE}{dT} = -\dfrac{\hbar c^5}{8 \pi GM T^2}$. In a qualitative way, one can also think that since the temperature of a black hole is bound to decrease with an increase in its area (larger the black hole, the cooler it is) and the area is bound to increase with an increase in its mass (energy), the specific heat capacity of the black hole has got to be negative.