Sounds like carb flu to me! Stick with it - I think people with these problems generally emerge feeling wonderful after two or three weeks. Make sure you give it a good 30 days of being strict paleo so you can properly assess the impact it has had on you.

I have to disagree on the sustainability. From what I've read this way of life could be a lot of sustainable than a grain based diet.

I'd probably recommend you try to have quite a few carbs by way of yams, sweet potatoes, squash etc as that should help youyr transition.

Increase your carbs, paleo does not need to be low carb. Add in root veggies. Low carb = low seretonin, = feeling horrible. Low carb makes kidneys excrete salt and water = feeling dizzy.

Leg cramps - could be lack of magnesium, or potassium. Add in some magnesium malate - it helps you feel better too.

If you have come from a high carb, low protein diet - it takes time to adjust. You will also be adjusting to burning more fat, less carbs. It is a big physiological change. So stick to paleo foods but increase carbs and decrease protein if you need to initially.

Take a lot of omega 3 - makes a big difference with some people in the transition stage as it decreases inflammation. You may be releasing omega 6 from cell membranes which is getting converted to inflammatory eicosanoid hormones. Or fats from fat cells that increase inflammation.

See this post by Dr K - he gives people 5HTP for a short time to counteract the issues with low serotonin, brought on by low carb. http://jackkruse.com/your-gutneurotransmitters-and-hormones/

Also make sure you are eating some fat. Try 1-2 Tbsp coconut oil or butter with each meal. It will help a lot.

Oh man the first two weeks are horrible. I thought, how can I work out feeling like this? Then what do you know, it passed and now I am as energized as ever.

While your daily banana will give you 12% of your RDA of potassium, you'll likely want a bit more than that to avoid cramping. Have a can of salmon (18%) or a small handful of spinach (16%).

As to your symptoms of being "suddenly lightheaded, nauseous, and my appetite vanishes... in-between my meals." This could be your adjustment to low carb, as people have suggested. Alternatively,e it could be you not eating enough calories (very easy to do on paleo). Or perhaps, as an ex-vegetarian you're still nauseated by meat and tacitly worried that if you eat any meat and fat it won't be "sustainable" and "could have harsh effects on my gall bladder and blood levels." You must realise that there's no reason to infer from being 'lightheaded, nauseous and no appetite' to 'my gall bladder and blood levels may be damaged!'

From looking at your blog- where you say that you perk up when you eat, but feel rough until you can find something else to eat- I think the evidence is pretty good that you're just not eating enough. Plausibly you're eating a small, 'normal' serving of meat, say 40g protein and 300 calories, and then feeling hungry until the next meal when you eat a pitifully small portion of your overall calorie needs again. If you're interested in weight loss then it might seem the last thing you want to do to purposefully eat more food when you have no appetite, but it seems quite likely that that's what you need, given that you are clearly 'hungry' physiologically, regardless. If you are going to inadvertently calorie restrict, then you will feel like you're in a starvation experiment (i.e. awful).

Thus, I suggest cooking up a large amount of meat: enough for a whole day's worth of protein (100-150g of protein). And eat as much of it as you feel like. Furthermore, don't try to get all your calories from protein, which can seem like the only thing you are allowed to eat on the paleo diet. Once you've had 15-25% of your calories from protein, then the other 75-85% are going to have to come from carbohydrate or fat (including some from your own body fat, of course). I note on your blog that you say that you're eating lean protein, which might explain it. If you are just eating lean protein and vegetables, then it's basically impossible to eat anything. You will have to either eat fruit and nuts (a bad idea imo, since they're high in fructose and PUFA), sweet potatos or some other kind of starch (not my preferred choice, but works for many, especially if you're very active and not looking to lose weight) or lots of added 'animal' fats (within which category I include coconut).

Almost 5 years LC-VLC Paleo here, had my gallbladder out 20 years ago. Absolutely no issues digestion fats but I had loads of issues as a SAD eater plus I WAS a T2 diabetic. My blood work is almost text book perfect, in fact my doctor was so impressed at my personal turn around that he is using paleo on a lot of his patients with spectacular results.

I just read your blog. I saw this list of guidelines you posted:

4-8 oz of lean protein such as chicken, lean beef, turkey, pork loin or seafood. Several servings of vegetables, either raw, steamed, or lightly cooked. Finally, round out the meal with good fats from Avocado, coconut oil, olive oil or a handful of un-salted nuts such as almonds, pecans, macadamias or walnuts.

I wouldn't worry about "lean" meat, particularly if you're buying non-factory-farmed. Feel free to cook your veggies in saturated fats like bacon grease or butter. Eat a ton of eggs; they're versatile and delicious. Don't be afraid to eat more than 2 at a time.. I eat almost 2 dozen/week. To reiterate what other are saying, you don't need to torture yourself with low-carb, unless you are trying to lose weight fast (for me personally, low-carb doesn't = weight loss, but it definitely reduces hunger and sugar/carb cravings, once yr over the hump).

Don't worry about gaining weight, it's highly unlikely to happen. Just forget about that for now and eat as much as you want.. but perhaps less often than you are used to.

Good luck! You can do this! And I feel confident that it will reduce the anxiety you mentioned in your blog. It might take longer than 30 days.. but it's well worth sticking it out. It worked for me!

Carb flu...

I recommend as others have said...

--eat more carbs like sweet potato since you're already lean

--cook your veggies really really well until your digestion improves

--for the discomfort eat some salty veggie or beef or chicken broth (best if you can boil some up yourself) or eat some salt...no I'm not kidding. You'll feel better within a few moments.

--for leg cramps eat potassium rich foods or supplement.

Once your fuel burning transitions you should feel better. If you were eating a lot of grains before you are in effect withdrawing from them.

I experienced nausea and loss of appetite as well and then it was just gone. Hang in there. It will pass.

These sound like symptoms you get when going from a high carb diet to low carb. Paleo doesn't necessarily mean low-carb, and you haven't said what your goals are (lose weight, gain weight, feel better, address some health issue, etc). If you don't want to eat low-carb, just add in some "good" carbs such as tubers, vegetables, and a modest amount of fruit.