Calorie issue or protein issue?

I'm no expert but my first thought would be that your not eating enough for that amount of exercise and that your weights are not heavy enough - I think it's meant to be higher weights for a shorter amount of time... i would love to hear your answers as well!!

I was in the same boat when I first started my workout regimen. I originally only did Zumba 3 days a week, but I didn't feel like I was getting the most out of my week at that level, so I decided to start doing resistance training (BodyPump/Kettlebell 4 days a week). When I first started I was only using a 10 lb kettlebell and 2.5 to 5 lb weights on my barbell in BodyPump. At the start, I was still losing muscle and fat at the same time (evident by the 3 lb weight loss every week for about three weeks). I obviously didn't have huge muscle mass gains at this level, it was more conditioning myself to getting to that point.
But now that I've been on a consistent schedule and I'm determined to gain muscle as well as lose the fat, I've seen HUGE improvements. I've been up-ing my weight almost every class (by 2.5 lbs when I can, if I'm uncomfortable, I'll stop and go back to my regular weight, no point in hurting myself to where I am laid up, but might as well give it a try. Up to 45lbs on the squat track [might not sound like much but when you're squatting that for a good 6 minutes straight through, you feel it] ).
My arms are completely different, they used to have that "jiggle" underneath, and had no definition at all. Now, the "jiggle" is almost gone and you can definitely see my biceps and forearms forming very nicely. Also, my legs have leaned out very well (my legs were never really "large", but the fat that was there has given way to nice muscle). I had a couple weeks where the weight didn't come as quickly as before, showing the muscle gain. Now my system is leveling out at around 1.2-2 lbs. loss each week.

I found that when I started a protein regimen after my resistance training days that I've seen the most improvement. The kind I have is Muscle Milk Light Cake Batter flavor (I know it's not the best, "organic" thing out there, but it tastes good and I've seen results with it, so I'm not complaining. Maybe down the road I'll switch brands.) But anyways, on the days that I lift, I do the full two scoop serving, it's 210 calories. I've put myself on a 1200 calorie/day program, and this fits in nicely on the days that I lift. [A slight disclaimer for myself- I never really tried to get in the right amount of proteins/carbs post-workout so this is why I saw the improvement when I started the protein shake.]

As far as a decision between increasing your calories or protein, it really isn't a huge decision to be made. Protein is calories. It's the same as sitting down and eating a piece of lean chicken that contains the same nutrients, just in a liquid form. Many people who choose protein shakes do so because of the convenience (my reason). The only difference is that your body digests the protein shake quicker because it is in a liquid form, which is beneficial pre/post workout because that's when your muscles need it the most (within 30 minutes if your post-workout). Your body uses protein and carbs to regenerate fibers in tissues as well as re-vamping your energy, so a quick-digesting protein shake is useful in this aspect, but it is not the only answer out there. If you choose to get your post-workout protein/carb calories in a meal, then so be it. Calories are calories. I'm sure there are people out there who swear that a protein shake is the end-all be-all, but a mean does just the same. Protein shakes are just a more convenient way.

Hope this helps!

I was in the same boat when I first started my workout regimen. I originally only did Zumba 3 days a week, but I didn't feel like I was getting the most out of my week at that level, so I decided to start doing resistance training (BodyPump/Kettlebell 4 days a week). When I first started I was only using a 10 lb kettlebell and 2.5 to 5 lb weights on my barbell in BodyPump. At the start, I was still losing muscle and fat at the same time (evident by the 3 lb weight loss every week for about three weeks). I obviously didn't have huge muscle mass gains at this level, it was more conditioning myself to getting to that point.
But now that I've been on a consistent schedule and I'm determined to gain muscle as well as lose the fat, I've seen HUGE improvements. I've been up-ing my weight almost every class (by 2.5 lbs when I can, if I'm uncomfortable, I'll stop and go back to my regular weight, no point in hurting myself to where I am laid up, but might as well give it a try. Up to 45lbs on the squat track [might not sound like much but when you're squatting that for a good 6 minutes straight through, you feel it] ).
My arms are completely different, they used to have that "jiggle" underneath, and had no definition at all. Now, the "jiggle" is almost gone and you can definitely see my biceps and forearms forming very nicely. Also, my legs have leaned out very well (my legs were never really "large", but the fat that was there has given way to nice muscle). I had a couple weeks where the weight didn't come as quickly as before, showing the muscle gain. Now my system is leveling out at around 1.2-2 lbs. loss each week.

I found that when I started a protein regimen after my resistance training days that I've seen the most improvement. The kind I have is Muscle Milk Light Cake Batter flavor (I know it's not the best, "organic" thing out there, but it tastes good and I've seen results with it, so I'm not complaining. Maybe down the road I'll switch brands.) But anyways, on the days that I lift, I do the full two scoop serving, it's 210 calories. I've put myself on a 1200 calorie/day program, and this fits in nicely on the days that I lift. [A slight disclaimer for myself- I never really tried to get in the right amount of proteins/carbs post-workout so this is why I saw the improvement when I started the protein shake.]

As far as a decision between increasing your calories or protein, it really isn't a huge decision to be made. Protein is calories. It's the same as sitting down and eating a piece of lean chicken that contains the same nutrients, just in a liquid form. Many people who choose protein shakes do so because of the convenience (my reason). The only difference is that your body digests the protein shake quicker because it is in a liquid form, which is beneficial pre/post workout because that's when your muscles need it the most (within 30 minutes if your post-workout). Your body uses protein and carbs to regenerate fibers in tissues as well as re-vamping your energy, so a quick-digesting protein shake is useful in this aspect, but it is not the only answer out there. If you choose to get your post-workout protein/carb calories in a meal, then so be it. Calories are calories. I'm sure there are people out there who swear that a protein shake is the end-all be-all, but a mean does just the same. Protein shakes are just a more convenient way.

Hope this helps!

I was going to reply but you said it all. I'm a big body pump fan too.

I think there are more of us in need of help to know how many fats, carbs and proteins are okay to loose fat and not muscle and we will appreciate your input

lift heavier - and don't lift every day (unless you're working different muscle groups - rest each muscle group at least a day between work outs).....

do strength before cardio (on strength days)

eat more. most people don't eat enough and then wonder why they aren't losing the weight they want to - you have to feed your body properly. and definintely eat a lot of protein.

I agree. Lift heavier. Just because you just started doesn't mean you should be lifting Grandma weights! Anything less than 5lbs is a waste of your time.

When you eat clean, you lose water faster. You lost 1/4 of a pound of fat last week, the rest was water fluctuation. I don't see anything to complain about there.

Honestly, are your cardio workouts intense? If you are working out 4-5 days a week, you really don't need to do more than 20-30 minutes of cardio if you are doing a high-intensity workout. 20-30 minutes of high intensity cardio is a lot more efficient than 50-60 minutes on an elliptical not breaking a sweat. Maximizing the amount of time you spend on a treadmill is really inefficient. I imagine there are other things you would rather do than spend two hours at the gym.

I would look into high intensity interval training. You get the best of both worlds.