Examples of hardness phase transitions
I'm not exactly sure if this is the type of problem you were looking for, but the phase transition of NP-Complete problems is a (by now) well known phenomenon.  See Brian Hayes's articles "Can't Get No Satisfaction" about the 3-SAT phase transition and "The Easiest Hard Problem" about the Number Partition Phase transition, for some popular articles on the subject.

Selman and Kirkpatrick were first to show numerically that the phase transition for 3-SAT was when the ratio of clauses to variables was at around 4.3.

Gent and Walsh were first to show numerically that the phase transition for the Number Partition Problem happened when the ratio of bits to list length was about 1.  Later this was proved analytically by Borgs, Chayes and Pittel.

Travelling Salesman, Graph Coloring, Hamiltonian Cycle, amongst others, also appear to have phase transitions for a suitable parameterization of problem instance creation.  I think it's safe to say that it is a commonly held belief that all NP-Complete problems exhibit a phase transition for a suitable parameterization.