There are certainly systems that have negative heat capacities, and in fact they come up all the time in astrophysics.
As a general rule, gravitationally bound systems have negative heat capacities. This is because in equilibrium (and remember we can't do classical thermodynamics without equilibrium anyway), some form of the virial theorem will apply. If the system has only kinetic energy $K$ and potential energy $U$, then the total energy is of course $E = K + U$, where $E < 0$ for bound systems. In virial equilibrium where the potential energy is purely gravitational, then we also have $K = -U/2$. As a result, $K = -E$, and so adding more energy results in a decrease in temperature.
Examples include stars and globular clusters. Imagine adding energy to such systems by heating up the particles in the star or giving the stars in a cluster more kinetic energy. The extra motion will work toward slightly unbinding the system, and everything will spread out. But since (negative) potential energy counts twice as much as kinetic energy in the energy budget, everything will be moving even slower in this new configuration once equilibrium is reattained.
At some level, this all comes down to what you're defining as temperature. Recall that temperature simply accounts for the flow of heat into whatever you've defined as your thermometer. If your thermometer couples to translational kinetic energy but not to gravitational potential energy, then you get the situation above.
I'll leave it to someone else to answer in terms of solid materials or inverted populations.