Yes, there has been a lot of work since Cheeseman, Kanefsky and Taylor's 1991 paper.
Doing a search for reviews of phase transitions of NP-Complete problems will give you plenty of results. One such review is Hartmann and Weigt . For a higher level introduciton, see Brian Hayes American Scientist articles  .
Cheesemen, Kanefsky and Taylor's 1991 paper is an unfortunate case of computer scientists not paying attention to the mathematics literature. In Cheeseman, Kanefsky and Taylor's paper, they identified the Hamiltonian Cycle as having a phase transition with a pickup in search cost near the critical threshold. The random graph model they used was Erdos-Renyi random graph (fixed edge probability or equivalently Gaussian degree distribution). This case was well studied before Cheeseman et all's 1991 paper with known almost sure polynomial time algorithms for this class of graph, even at or near the critical threshold. Bollobas's "Random Graphs"  is a good reference. The original proof I believe was presented by Angliun and Valiant  with further improvements by Bollobas, Fenner and Frieze . After Cheeseman, Kanefsky and Taylor, Culberson and Vandegriend  published a paper giving an algorithm that in practice performed extremely well for all Erdos-Renyi random graphs, even near the critical threshold.
The phase transition for Hamiltonian Cycles in random Erdos-Renyi random graphs exists in the sense that there is a rapid transition of the probability of finding a solution but this does not translate to an increase in "intrinsic" complexity of finding Hamiltonian Cycles. There are almost sure polynomial time algorithms for finding Hamiltonian Cycles in Erdos-Renyi random graphs, even at the critical transition, both in theory and in practice.
Survey propagation  has had good success in finding satisfiable instances for random 3-SAT very near the critical threshold. My current knowledge is a little rusty so I'm not sure if there's been any large progress of finding "efficient" algorithms for unsatisfiable cases near the critical threshold. 3-SAT, as far as I know, is one of the cases where it's "easy" to solve if it's satisfiable and near the critical threshold but unknown (or hard?) in the unsatisfiable case near the critical threshold.
My knowledge is a bit dated now but the last time I looked at this subject in depth, there were a few things that stood out to me:
- Hamiltonian Cycle is "easy" for Erdos-Renyi random graphs. Where are the hard problems for it?
- Number Partition should be solvable when very far in the almost sure probability 0 or 1 region but no efficient algorithms (to my knowledge) exist for even moderate instance sizes (1000 numbers of 500 bits each is, as far as I know, completely intractable with state of the art algorithms).  
- 3-SAT is "easy" for satisfiable instances near the critical threshold, even for huge instance sizes (millions of variables) but hard for unsatisfiable instances near the critical threshold.
I hesitate to include it here as I have not published any peer reviewed papers from it but I did write my thesis on the subject. The main idea is that a possible class of random ensembles (Hamiltonian Cycles, Number Partition Problem, etc.) that are "intrinsically hard" are ones that have a "scale invariance" property. Levy-stable distributions are one of the more natural distributions with this quality, having power law tails, and one can choose random instances from NP-Complete ensembles that somehow incorporate the Levy-stable distribution. I gave some weak evidence that intrinsically difficult Hamiltonian Cycle instances can be found if random graphs are chosen with a Levy-stable degree distribution instead of a Normal distribution (i.e. Erdos-Renyi). If nothing else it will at least give you a starting point for some literature review.
 A. K. Hartmann and M. Weigt. Phase Transitions in Combinatorial Optimization Problems: Basics, Algorithms and Statistical Mechanics. Wiley-VCH, 2005.
 B. Hayes. The easiest hard problem. American Scientist, 90(2), 2002.
 B. Hayes. On the threshold. American Scientist, 91(1), 2003.
 B. Bollobás. Random Graphs, Second Edition. Cambridge University Press, New York, 2001.
 D. Angluin and L. G. Valiant. Fast probabilistic algorithms for Hamilton circuits and matchings. J. Computer, Syst. Sci., 18:155–193, 1979.
 B. Bollobás, T. I. Fenner, and A. M. Frieze. An algorithm for finding Hamilton paths and cycles in random graphs. Combinatorica, 7:327–341, 1987.
 B. Vandegriend and J. Culberson. The G n,m phase transition is not hard for the Hamiltonian cycle problem. J. of AI Research, 9:219–245, 1998.
 A. Braunstein, M. Mézard, and R. Zecchina. Survey propagation: an algorithm for satisfiability. Random Structures and Algorithms, 27:201–226, 2005.
 I. Gent and T. Walsh. Analysis of heuristics for number partitioning. Computational Intelligence, 14:430–451, 1998.
 C. P. Schnorr and M. Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. In Proceedings of Fundamentals of Computation Theory ’91, L. Budach, ed., Lecture Notes in Computer Science, volume 529, pages 68–85, 1991.