Four decades ago, several scientists suggested that the impossibility of any evolutionary process sampling anything but a miniscule fraction of the possible protein sequences posed a problem for the evolution of new proteins.  This potential problem-the sampling problem-was largely ignored, in part because those who raised it had to rely on guesswork to fill some key gaps in their understanding of proteins.  The huge advances since that time call for a careful reassessment of the issue they raised.  Focusing specifically on the origin of new protein folds, I argue here that the sampling problem remains.  The difficulty stems from the fact that new protein functions, when analyzed at the level of new beneficial phenotypes, typically require multiple new protein folds, which in turn require long stretches of new protein sequence.  Two conceivable ways for this not to pose an insurmountable barrier to Darwinian searches exist.  One is that protein function might generally be largely indifferent to protein sequence.  The other is that relatively simple manipulations of existing genes, such as shuffling of genetic modules, might be able to produce the necessary new folds.  I argue that these ideas now stand at odds both with known principles of protein structure and with direct experimental evidence.  If this is correct, the sampling problem is here to stay, and we should be looking well outside the Darwinian framework for an adequate explanation of fold origins.