It’s been awhile since you first posted, mommyof3inidaho, but I wanted to share a few thoughts.
First, I agree with elfman5150 about the flora being severely altered while on a paleo diet. Food with high levels of ‘prebiotics’ such as bananas, potatoes, apples, and most other tubers and fruits will help selectively feed the ‘good bugs’ and give them the opportunity to re-take their appropriate spot within the circle of life in the gut. Eating ‘junk food’ tends to feed stuff very UNselectively, which means UNTIL your good bugs are up to speed, junk food will exacerbate dysbiosis and result in any number of symptoms including what you are having. I know some people do well with PRO-biotics (supplemental bacteria), but I think ‘PRE-biotics’ (foods with specific types of fibers) are better in your case since there is no evidence that you don’t have the proper bacteria, just that you need to start feeding them after this long period of starving them. It will take months to re-establish proper flora composition.
You can read my reply to another post here for more info on this kind of thing:
http://180degreehealth.com/180forums/topic/gut-bacteria-weight-loss/
Second, I think electrolytes/fluid balance have a huge impact on headaches and so on. Sodium, Potassium, and Fluid must be in proper balance. As a rule, too much sodium and/or not enough potassium can cause headaches. Too much potassium and not enough sodium can cause lethargy and/or hypothermia and/or anxiety issues. Drinking water modulates all of this by lowering both potassium and sodium in the blood, and potentially lowering potassium within cells. What I mean to say by all of this is that you may try displacing some ‘junk food’ with bananas and fruit and potatoes (increasing potassium) to see if that helps. If it is to help, you should notice it within hours to days. If it hasn’t helped within a few days, forget it.
Third, I wanted to mention nutrient deficiencies and dynamics. Carbohydrates and the resultant insulin surge stimulate the uptake of a wide variety of nutrients (potassium, b vitamins, and other stuff) INTO cells, OUT of the blood. I think paleo and other restrictive diets tend to commonly be low in certain nutrients. However, it is UPON increasing carbs that the deficiency manifests itself because only then will the blood level of these already-borderline-depleted nutrients drop (as they are shuttled into tissues). Some of the most prime culprits are potassium, magnesium, thiamin, and other B vits. You may want to try supplementing some magnesium and a decent b complex to see if that helps your headaches. Fruits and tubers should give you plenty of potassium. [As a brief albeit important aside: I’m not fond of b complexes with thiamin (B1) as ‘benfotiamine’ for refeeding deficiencies since this form is a synthetic fat soluble nutrient that does not follow the same pharmacodynamics as water-soluble thiamin. So the b complex should have B1 as Thimain HCL.]
Some supp ideas could be the following (just ideas to consider):
The latter is a full multivitamin but I like it because it has natural folate and b12 and because it has more thiamin in proportion to other B-vitamins than most supps.
I hope experimenting around with these things will help lead to the promise land. Please keep us all informed on your progress!