First, I replied to a post by Matt below. Then, I noticed that Calvin had invoked a similar theme. The issue: protein folding and random walks.
Protein folding is not an entirely "random" walk. If it were, then there would be no resolution to Levinthal's "paradox". However, this does not mean that the concept has no use for protein folding.
Modern thinking on the issue is that protein folding can be thought of as a random walk on a "funnelled" landscape: see e.g. the following 1997 perspective by Ken Dill:
A slightly more technical paper on the resolution of Levinthal's paradox has been written by Zwanzig, Szabo and Bagchi