Materials that exhibit entropic elasticity will theoretically exhibit this effect. For example, elastomers that at a temperature far greater than the glass transition temperature.
In entropic elasticity, stiffness arises not from stretching mechanical bonds, but by decreasing the entropy of the polymer chains in the material. A derivation of this phenomenon is beyond the scope of this question, but here's the punchline:
The initial shear modulus of the material is proportional to the absolute temperature. This fits the bill for a material that "softens when it gets colder."
Here is a link to the Wikipedia page for rubber elasticity. This phenomenon is described in more detail here.
http://en.wikipedia.org/wiki/Rubber_elasticity