At 5'6" and 115 lbs you would have been at 18.5 BMI*. That's the very low edge of normal. Normal weight = 18.5–24.9 At 130 lbs, you're still at 21 BMI. You could be gaining into a healthier weight range.

Doing weights would shift any fat gain to muscle gain. It's possible you were and still are "skinny fat."

*BMI is not the best indication for several reason, including the skinny fat issue, but it is indicative, especially since you aren't real active. There are more accurate ways to measure body fat % which is a better indication than BMI. The scales that are supposed to do this are not very accurate. http://en.wikipedia.org/wiki/Body_fat_percentage#Measurement_techniques

ADDED: If you're doing paleo to be able to become pregnant, you WANT your BMI to be higher. IIRC, 22 BMI is about right. Dragonfly is the best source of info around here for those kinds of issues.

ADDED: It's damn hard to get adequate nutrients, especially if you want to get pregnant at only 1400 calories/day. Get more active and eat more.

ADDED: It's really hard to track calories accurately from memory. Try tracking daily for a week or so if you did it from memory.

lilliputty~

My condolences on your miscarriages.

(Just so you know, I wrote this without reading the other answers/comments!)

Excessive abdominal fat in otherwise normal weight women is usually a sign of hormonal imbalance. Sometimes excess cortisol, sometimes estrogen dominance. Sorting this out will help you release the belly fat as well as helping your fertility.

If it's cortisol-related, a Paleo diet will help to a certain extent, but a few other things need to be dialed in:

Sleep. So essential. Read this: http://drgominak.com/vitamin-d

Stress reduction. Excessive life stresses, including excessive exercise, can ramp up cortisol in women too much & contribute to fat gain. Meditation may be helpful, if this is the case. Gentle daily walking/movement (1+ hour) & some resistance training twice a week is usually enough to maintain a balanced metabolism at a normal weight.

Vitamin D level. Ideally in the 60-80 ng/ml range for hormonal balance.

Magnesium. Many folks cannot get enough through diet. 200-600 mg Magnesium Glycinate before bed may be helpful. Mag is also a necessary co-factor for D.

More details here:http://www.sondrarose.com/optimum-fertility-nutrition

Also, Estrogen dominance may be a reason for your increased belly fat at age 37.

Reducing environmental xenoestrogens is key: http://www.sondrarose.com/optimum-fertility-environment

You may want to research topical bioidentical Progesterone cream (lots of info on Dr. Lee's site.)

If nothing else has changed, you are eating more calories than before, and more than you burn, plain and simple. There is magic in Paleo, in my experience, with mental things and hormonal stuff like hunger and sleep, but it doesn't over-ride the above statement.

Are you more or less hungry on Paleo? Do you eat bigger or smaller meals? Do you eat more or less often? Have you tried Intermittent Fasting?

Eat less food every day, period. Rather than count calories, get a little gram scale and consistently eat the same amount of a particular food when you eat it. Keep a journal. Once a week, cut that amount down by a little and you'll find the point where you start losing fat. Keep cutting amounts every week until you get low enough to keep fat loss going but don't feel starved. Going slowly keeps your mind and body from freaking out and hitting the cupboard.

Eat fatty meat or eggs with non-starchy veggies regularly. If you are getting fatty cuts, you don't need any added oil or cream. In my opinion folks go over board with that.

Eat carbs ONLY after some exercise, preferably that which elevates your heart rate a bit. You said you only eat carbs once a week. Try having a good bike ride, hike, or good brisk and long walk on the weekend and have your carbs right after. In my experience, eat fat and carbs away from each other; taken near each other is asking to gain fat.

Make sure you are hungry (dietary fat burned out of your system by that point), when you eat carbs, and eat them with very lean protein like top round steak, lean pork, or fish. You could eat another meal after that, depending on the timing, but it should again be carbs and lean meat, not another fatty meal that day after you've eaten carbs. The carbs raise your insulin for hours, and shut off lipolysis to an extent, so dietary fat you eat after that will be more likely to be stored than burned. The next day, go back to fatty meat and veggies and no carbs.

My .02

And I agree with the above advice, you cannot expect good body composition without hitting some hard exercise. Inactive is not paleo; our ancestors did a lot of exercise, and we are made for it.

OMG, what horrible answers. IF your gaining abdominal fat, the reason for this is simple. You are consuming more calories (think fats) than you are burning. 15lbs and 2 dress sizes says you are gaining weight not only on your stomach but you hips, butt, and legs as well. Increase your activity and decrease your calorie consumption and watch the scale go back down. It really is THAT simple.

YES! The crybaby (fat) down voters are out in force on this one!!

What's your activity level like? Are you sedentary or quite active? Is your day job desk-based? Have there been any other factors that could be attributing to the weight gain? Any stressful situations, disrupted sleep pattern, change in contraception etc.?

You mentioned sweet potatoes - how often are you consuming starchy carbs, and at what sort of time (post workout, at night, mornings?)

Are you consuming leaner cuts or fattier cuts of meat? How do you feel on the diet in general, are you happier since having gone on the diet or has it been uncomfortable to give up your old food choices? How often a week (on average) do you fore go the regime? Are you finding you're having to consume more, calorie-wise, to remain satiated? Have you done any calorie/macro tracking? What's your average uptake in calories been?

Sorry to answer your question with questions - wouldn't want to answer your question without a healthy understanding firstly.

I agree with Karen. One misconception (and one I still struggle with getting right) is that Paleo/ Primal style of eating is NOT about weight loss. Many of us started heavy, and so weight loss is our motivator, but you actually started under-weight.

Paleo/ Primal style of eating is about allowing our genes to naturally find our healthy set point. For you, going from 115 to 130 could be very healthy.

Now, for the stomach, try throwing in some simple exercises. What this will do is help your body maintain it's level of health. However, where we hold our fat is very personal, and there's nothing you can do about that. It seems like, for you, your fat stores are around the belly. Some women it's distributed throughout their body, other's it goes "straight to the hips", etc. There's nothing you can do about your body's composition other than eat right, exercise a bit, and be proud of who you are.

Here's a quick, easy, body weight workout that a beginner could do easily -- you mentioned you have a desk job -- Try doing some IF (don't eat after dinner, skip breakfast), then throw this into a lunch time workout 3 days a week, followed by a high protein meal (either a shake or lunch). Using your lunch hour to workout really helps break up the afternoon!!!

http://www.marksdailyapple.com/bodyweight-workout/#axzz21RdQ7hne

I always think sugar and fruit when inches around the waist is an issue. Is it possible your moderate amounts have inched their way up over the year? Don't skimp on the healthy fats, though, especially if your intention is to have children.

It sounds like you are insulin resistant, get a blood test.