Eat MORE fat & more carbs! Doesn't sound like you are getting enough calories. And don't limit salt!

I would say if you're having bleeding intestines and you're still having little cheats with grains "5% little cheats like 1 small slice of garlic bread or 1 marshmallow once a week" (Marshmallows are usually coated in cornstarch) THAT's the reason you still feel like crap. For your health you MUST eliminate all grains, not even a little tiny bit every once in a while is OK. I've read that it can take your gut MONTHS to recover from grain exposure, so you haven't even been grain free long enough to start feeling better. You really have to commit to NO grains--NONE.

And watch for hidden grains in the foods you eat. I looked up ingredients for light mayo with olive oil and they ALL have STARCHES in them as well as soybean oil--in many cases those starches come from GRAINS. These are no no's. Try making your own mayo at home, it's not that hard and you will know exactly what goes in it. Never skimp on good fats for manufactured "lite" foods full of industrial oils, starches, and unnecessary sugars. They are NOT paleo!

To combat induction flu (if that's what you have) you need potassium and sodium. Broth is a good source, but make it homemade because most commercial broths and bullion cubes have added starches, and often MSG.

If you still feel bad after another week or two of making these changes, you should look into an elimination diet like GAPS.

And are you taking/eating any probiotics? You need to heal your gut, and they are crucial. If your gut can't handle lacto fermented veggies like sauerkraut and pickles right now (and it sounds like it may not), you can get the benefit just by putting the sauerkraut or pickle juice into your broth and other recipes.

I think you might be underestimating your small cheats. When we spread them out and do little bits here and there, we can make a lot seem like a little. I can see lots that you're eating that may not be the best choices with your health concerns, like the melons, canned beans, nuts and dried fruit.

Understand that I'm not trying to make you feel bad, for all of us, it takes a huge amount of effort to break old habits, root out the bad choices, and be really honest with ourselves. And of course, cheating is exceptionally human.

Concentrate on whole foods, not canned, and eat until you're full. Add more fats, like everyone says. Reveiw the shopping lists at Whole30, marksdailyapple.com, or whatever sites you like, and switch out the foods that aren't working. Sleep, eat, relax. It's not a test. I'm sure it will change for you.

Sounds like you're still in the throes of carb flu. Give it a couple more weeks!

Consider trying something like the "perfect health diet" with the addition of safe starches like sweet potatoes and white rice. Would help bring up the energy levels for now.

Meat/bone broth with nice mineral salt might help against low-carb flu.

Another question - should it be low carb? Maybe adding safe starches (potatoes, rice, yams) can be a good idea.

Most people feel like crap for the first 3-4 weeks of Paleo. There are lots of theories why, but I don't think there is anyway around it. You just have carry on and get through it. You will feel better I promise. I agree with the other comments, clean up your diet even more and eat more fat. When I first started Paleo I ate coconut oil straight out of the jar - especially when I was craving carbs - and it always made me feel better. Good Luck

Diet isn't everything. If you don't manage your stress, healthy food won't matter. You'll be susceptible to illness and disease, depression, adrenal fatigue, and a host of other health problems.

Take time throughout your day to practice stress management. It's not that you have to change your life, you just need to allow your body to recuperate after your stress hormones become elevated. Here are some tips that you can easily incorporate into your daily schedule:

http://radcliff.hubpages.com/hub/6-Ways-to-Relieve-Stress-Without-Changing-Your-Schedule

Add more healthy oils -- cool the eggs in coconut oil or a good grass fed butter. Add bacon, tastes good and will give you a boost!

Agree remove the cheats, corn, and try to cut down the berries and fruits. I am a little over two weeks in and I only drink water and have had no issues with cravings. Not everyone is the same but when I eat fruit even berries I am hungrier. If I eat protein/veggies/fats I am full and energetic.