A recent article in New Scientist called "Let Them Eat Dirt" propounds a
new theory based on evolutionary reasoning and research on immunity to
the effect that lack of exposure to dirt and infectious agents early in
life can predispose people to allergies and autoimmune diseases. The
full text of the article is available at www.newscientist.com - suggest
you read the entire text before commenting... Here are some excerpts:

"...a growing number of scientists who are warming to the paradoxical
notion that our obsession with cleanliness and hygiene carries a hefty
price tag. They suspect that our growing separation from dirt and germs
is behind the rapid rise in asthma in the US, Western Europe, Japan and
Australia, and may be triggering other allergic diseases, too. Our
hygiene fetish could even be pushing up the incidence of more serious
autoimmune diseases such as diabetes and rheumatoid arthritis.

The argument goes like this. During most of evolution the immune system
was bombarded with dirt and germs from the moment each newborn infant
hit the cold light of day. So the immune system learnt to make the most
of the situation, relying on the relentless onslaught to help forge and
maintain its sophisticated network of chemical pathways and specialised
immune cells. According to what is known as the "hygiene hypothesis", it
is when you remove that stimulation--particularly during infancy--that
things go haywire. "

".... In the past few years, immunologists have discovered a mechanism
involving immune cells called Th cells that could explain how too few
germs might make the immune system respond inappropriately to harmless
cat dander, mite faeces and pollen. Th cells behave like M, the
behind-the-scenes spook who gives 007 his brief. When the immune system
is working properly, Th1 cells send out messengers called cytokines that
instruct immune cells infected with bacteria or viruses to kill their
cargo. Th2 cells send out cytokines that direct an entirely different
set of operatives--including one rapid response unit whose main mission
is to stop parasites from penetrating the wall of the gut. In this case,
the Th2 signal unleashes "IgE" antibodies and summons mast cells and
eosinophils to the area of infection. Then, as the antibodies bind
immune cells and parasites together in a clump, the eosinophils release
toxic chemicals to poison the parasite, and the mast cells squirt out
histamine. The histamine triggers a flood of mucus to wash the dying
parasites off the gut wall.

"Allergens can induce either a Th1 response or a Th2 response, but only
Th2 causes runny noses, itchy eyes and wheeziness because it treats the
allergens much like dangerous parasites. But what makes the immune
system decide to use its Th2 response against allergens in the first
place? That's where the hygiene hypothesis comes in.

"The immune system's choice depends to some extent on the balance of
power between the two different sorts of cellular spooks--the Th1 and
Th2 cells. Which of the two gains the upper hand appears to depend on
how many bacteria and viruses the immune system has to deal with both
in  childhood and as an adult. In an adult, most bacteria set off the
Th1 response, which curbs the cells that send out Th2 signals, tipping
the balance away from an allergic response. "

In my opinion, this is but a partial explanation for the increase in
asthma and allergies. I agree with "Neanderthin" that exposure to
nonpaleo foods has alot to do with it.