I have been thinking about this myself. When paleo people talk nuts you usually hear concerns about:
Omega6 ratio. I am not the expert here but perhaps there is a difference between grain fed sedentary animals (and certainly processed vegetable oils) and nuts that fall from a tree in a natural state. There are different types of cholesterol; could there be more harmful and even beneficial omega6 fats?
Calories. OK sure nuts are calorie dense and if trying to lose weight obviously counter-productive. 2 Tb almond butter has nearly 200 calories which is 1.5 cans of tuna! A few days ago made some almond butter from scratch. It took a lot of nuts to make a small amount of almond butter. If there is a jar of almond butter around I can eat a couple spoons, but if eating the whole nuts I would never eat that many. Nut butters are the paleo pastry, ie processed like white flour. Eating them whole or perhaps even better immediately after shelling it is much harder to overdo.
That said I think there are some benefits. As NastyBrutishandShort mentioned, there are some positive studies. Here is a quote from a recent one:
"Our findings confirm the results of epidemiological studies showing that nut consumption lowers coronary heart disease risk and support the inclusion of nuts in therapeutic dietary interventions for improving blood lipid levels and lipoproteins and for lowering coronary heart disease risk," write lead investigator Dr Joan Sabaté (Loma Linda University, CA) and colleagues in the May 11, 2010 issue of the Archives of Internal Medicine."
Dr Al Sears is not often cited in the paleo scene but he has been recommending a paleo-like diet for many years (in addition to interval exercise) and he recommends them. Most nuts contain very high levels of magesium which seems to be a very important mineral and one of the few things that a lot of paleo people are willing to take as a supplement.
Native Americans ate hazelnuts, walnuts, hickory nuts, pine nuts, pecans; Aboriginal people ate macademias; almonds are native to the middle east but any gatherers would have feasted on them. Lastly, even when meat was plentiful most hunter-gatherers still ate a lot of food from plants and surely this would have included nuts. I think this is an interesting point. OK yes you can survive on meat alone and certainly couldn't on nuts alone, but still this suggests optimal is meat + plant foods including some nuts.
Bottom line a handful as snack or with meal seems like a good idea if you aren't trying to lose weight.