So you started a new exercise routine that is burning more carbs, guess what the body's response is?
Store more carbs.
Carbs store with water in muscles. You got what your training asked for. Likely increased blood volume.

Both TDEE deficit method and MFP method will end up about the same as far as number - IF, if you take the same reasonable deficit in MFP as TDEE would cause.
Which you aren't.

In addition, you are creating bigger deficit only eating back 1/2 exercise calories.

Depends on your motivation. Does needing to burn more in order to eat more motivate you most. Or does have a plan with expected exercise amounts to eat the same daily motivate you the most.
And which is easier for planning?
Which goal will you really meet? Keep missing your goal on either and it's NOT better.

Like your do walk, if you actually are honest on the time, and pace, is very accurate for calorie burn, more than a HRM would be.
Log it honestly and eat it all back.
The C25K, if logged honestly, is the same thing, log and eat it all back.

You also need to separate 2 things that are very different purposes.

Diet is for weight loss - done right just fat loss, done wrong muscle mass loss. You are doing more of the latter part there sadly.
Exercise is for body improvements and heart health - done right can support fat loss, done wrong can encourage muscle mass loss. If those DVD's is cardio only, you are getting the latter one here too, not good combo.

Only thing exercise does for diet is increase the amount you burn daily, so when you eat less than that, it is hopefully high enough you'll still adhere to it. Compared to eating level when you don't exercise, could be so low you'd have trouble following it.

If you do the TDEE method because you want 1 number daily, and that motivates you to do your workouts, or they are being done no matter what, then count your walking time as 1/2 what you actually do - because it's not a heavy workout.

http://www.myfitnesspal.com/topics/show/1018770-better-rough-tdee-estimate-than-5-level-chart

Thanks everyone! I suspected I may not be eating enough so I'll be interested to see how eating more works out over the coming months. I'd not thought about 2 DVDs being too much but when alongside the dog walking I guess it is!

I have set my goal as TDEE -15% and will be doing 3-5 hours a week of exercise (likely 5) with 2 rest days. That brings my daily calorie goal as 2413.

Thanks for the replies!

Depends on how long and intense the DVD's are with current level of fitness.

They could be 2 x 30 min of walking along with Leslie - that is not intense nor too much if you've been walking the dog for years already.

They could be 2 x 60 min of Insanity and P90X - that could be way too much especially if you just started walking the dog too from totally sedentary just a month ago.

And be aware when adding the time, walking 1 hr is obviously not the same calorie burn as running 1 hr as lifting 1 hr, ect. Walking counts as 1/2 time in those charts - or you with lots of walking will be overeating. 1 hr of walking counts as 30 min in the TDEE charts.

Extra fat gain isn't a benefit in any way.

Heybales is right...it does depend on the length and intensity of the DVD's. Those are shorter DVD's time wise, but still physically exerting. I think where I sensed your tiredness/frustration was when you said "I worked my backside off doing exercise" and usually when you feel that way (especially when not eating enough to fuel you workouts), then you need to back off the exercise a little or for sure eat more to fuel those workouts if you want to stay at that activity level...otherwise at some point your body will just physically get tired and you won't be able to continue at that pace...something has to give you know. I have several Jillian DVD's and shreds and they are pretty intense! If you enjoy it, then just make sure to eat according to your activity level. And the dog walks are just adding to your NEAT - which is still contributing to a too large deficit if you are already not eating enough!

Still going to do 5 days of 50 min of DVD workouts?
Still 7 days of 40 min dog walk, or about 140 min TDEE time?
Still doing C25K for the 30 min 3 x weekly?
This is assuming an otherwise sedentary desk job/commute for 45 hrs weekly, if actually more active than that counts more too.

250 min + 140 min + 90 min = 480 min, or 8 hrs weekly?

The normal TDEE chart uses the formula for hours

(Weekly movement hrs x 0.0875) + 1.2 = Activity Factor

Activity Factor 1.9 x 1830 BMR = 3477 TDEE

TDEE 3477 x 0.85 = 2955 daily eating goal.

Sounds like your activity will still fall into the 5-6 hour range, using Scooby with 15% cut would be 2689 daily goal.

Yes, you would eat 2689 even on rest days! When using TDEE method, it spreads your activity calories over the entire week.