What's your 25m stroke count?

You should be exhaling the entire time your face is in the water, not holding your breath.  I know you said you're not gliding, but if you're running out of air you either have a VERY slow turnover, or you're gliding. 

I'm guessing a few rounds of golf could help you.

It can be a fun drill to do.  Your "golf" score is your time plus number of strokes.  Just like real golf, your goal is to get the lowest score possible.

I haven't seen the TI video or read the book but have had a couple of lessons from swimfortri in London and they seem to use similar philosophy. ie long smooth strokes to make the swim more efficient and leave more in the tank over a given distance. first time I went my stroke rate was 25 per 25m and looking at the dvd of my stroke my form was terrible. they worked on streamlining me and better rotation to help with the distance per stroke.

A bit of practice and my rate dropped to 20-21 per 25m and time for 100m fell from 2:00 to 1:50.

Another lesson and more practice and I am now doing 18 strokes per 25m in 1:40. The best thing is I can swim at 2:00 per 100m over Olympic distance no problem whereas I struggled to do 800m at that pace when I started my first sprint.

Agree totally with Trimybest, you should do golf scores. If breathing every 3rd stroke is too long per breath mix it up and do every 2nd stroke for a couple of lengths to get your form back. 

Yup ..... one of the reasons faster people are typically anti-TI.  It teaches you to swim, it doesn't teach you to swim fast .......

After 3 one on one lessons with a swim coach I could get it down to around 14 or 15 when I concentrated on it and didn't worry about speed in the 25y pool, but I'm typically in the 18 - 19 range for normal swims.

When I'm doing a longer distance set (500-1500 yards) in a 25 yd pool at a decent pace for me (i.e., 1:25 per 100 yd), I'm at about 15-16 strokes per 25 yds.  Sure, I can drop it to 10 strokes per lap for drills, but that doesn't really translate into regular swimming for me.  When I'm doing faster, shorter sets, say 100's at a 1:15 or faster, I'm sure my stroke count goes above 15, probably to 17 or 18.

Don't obsess over stroke count, but get it down to a relatively efficient level over time.  In a 25 meter pool, you should be below twenty strokes per lap -- something around 15-18 would be just fine.

It also depends on how tall you are, the taller the better in terms of stroke count. Also, if you're dragging excess weight, like floating anchors (aka baggy shorts) or lots of extra body weight, then that will slow you down.

When I actually train for the swim I usually hold around 1:50/100 with 15 strokes/25 for 2500-3000 straight (yards). If I swim faster my stroke count goes up.

(I'm a tall and lanky 44-year old female. On winter running-focused plan right now, thus not swimming much, only for recovery. Training to improve my swim by a few seconds is not efficient: I usually win my AG in the swim, stay pretty high on the bike... and then lose the podium on the run.)

Thanks all for the pointers. Will incorporate lots of them.

 In terms of my swimming, I do exhale pretty continuously during the face-down portion. I think I'm frustrated because as I mentioned, oxygen acquisition is a clearly limiting factor for my swimming. My arms never get tired at the paces that I'm swimming (they do only if I sprint for 100m-200m), but I get so short of breath that I can't maintain the low stroke count. 

I don't think it's my VO2 as well - I'm in pretty good shape after lots of marathon traning (I run the 5k in 18:00 and marathon at about 7:15/mile). I do wonder if my lungs are small or if my heavier body mass (BMI=25+) make it more important for me to take more breaths which may be limiting my swim.

I tried to throw a few more strokes in, but I don't think it's as good for my technique. I suspect that I really do need to just spend a LOT more time in the pool to build up the upper body capillaries that I'm sorely lacking. Of course, any other pointers to make this faster are welcome!

Ok - I'm a slow swimmer (2:00/100m for 1000m+ swims), but from my limited experience, I think you can get a really good start on cutting down stroke number without a coach if you're way in the high 20s-low 30s per 25m.

I found that by reading Total Immersion carefully, and then doing most of the drills, and then "obsessing" about the flat body position and smooth strokes that he comments on in the book, my stroke number went  down from 25ish to 16-17 in a SINGLE workout - this is "typical" for swimmers who start for his Total Immersion technique.

Within a week, I was down to pretty much the stroke number I have now, which is about 14-15/25m. Unfortunately for me, the speed doesn't seem to correlate with stroke efficiency yet, but I'm counting on it to happen later. In fact, I definitely got slower for the first 3 weeks with the new stroke - which was also expected and warned about in the book due to the unfamiliarity with the technique. 

For me at least, those "big and long" powerful strokes really cost me in terms of energy consumption. Plus, I can't "huff and puff" rapidly as I would on the run or bike since the stroke is so long. In fact, the TI stroke is so powerful and long that it feels like I'm pulling up a hill in the big gear on a bike, and I wish I could "gear down!" to get some more smaller breaths! More training to come...