Hello Ozzie, nice to have you in. I wonder from your
experience if you didn't add in something to your usual diet
that was allergenic? Since you sound like you were doing
pretty well on your former diet, I suggest the old "if it
ain't broke don't fix it" proverb holds true.  I might try
slowly, one at a time, eliminating non paleo foods, or
adding a greater variety of paleo OK foods. Go slow, one at
a time, see what effect it has.

For most of us the key "bad" food is wheat.  It seems to be
the cause of a lot of peoples symptoms. I figure my
ancestors have been eating wheat less than a thousand years,
much less for the more northern European ancestors. Wheat
certainly seems the worst to me. Oats and rice don't seem to
have any immediate negatives, so I occasionally eat them.

Another point might be candida. If you were cutting back on
carbohydrates, your gut flora might have been changing. Some
people claim that when the yeast dies off it can cause a lot
of the symptoms you described.

It sounded like maybe you are not a big meat eater,
mentioned only lamb. If you were vegetarian or near
vegetarian, it can take a few weeks to get back into the
proper enzyme production to digest meat well. Eat a variety
of meats, not just fish, fowl, but also red. Don't forget to
eat lots of eggs. Increase gradually the quantity. Meat is
the basis of the paleo diet practiced by most of the people
on this list.

It really does sound as if your fat intake was low. Eat
fatty meat, don't trim the fat. Get a variety of fats, but
particularly animal, red meat based. Your emotional troubles
should clear up in a few days  :--)

If you are very slim, it is not surprising that you will
gain weight on this diet. Your muscle tone should be
improving as you move toward you ideal build. It may be that
you are underweight now.