Name a substance that will change from liquid state to solid state on heating.
And remaining chemically unchanged? Nothing does that.
You could have your ceramics which change from a liquid structure to a solid structure, but that's with the formation of bonds on heating and all that.
Is it possible for some sort of solid solution to have a liquid phase at a lower temperature than a solid phase?
It is possible, even for reversible transformations. It's only required that the high-temperature phase (the solid) has a higher entropy than the low-temperature phase (the liquid). As you can imagine, this is pretty unusual. I seem to remember that it's been demonstrated in some carefully designed polymer systems, though. Will look to see if I can find the details.
Ah, I found it: Plazanet et al., "Freezing on heating of liquid solutions," J Chem Phys 121:5031 p5031 (2004), discussed http://physicsworld.com/cws/article/news/20325" [Broken]. But a look at the subsequent literature indicates that the physics is still being worked out.