Running into trouble....

i think initially you will experience some breathing issues while you run for a little while.  Those couch -> 5k programs are really great in that they really force you to walk/run a lot before they make you run the entire distance.

I started my running career with a couch to 5k with no more running behind my belt than 8th grade cross country.  My suggestion is to STICK WITH IT to the finest detail.  Don't get bored and jump ahead a week because you are breezing through the workouts with minimal sweat.

Also do you have a history of asthma?  Your lung capacity will take a little while to catch up and clear all the damage done from smoking but it will happen.  Shortness of breath is normal while/after running.

Personally I like to take deep rhythmic breaths.

Stick with it and you'll notice that you feel out of breath a lot less!

I began my couch to sprint plan on May 18.  At that time I had just quit smoking, had never run, was (still am) overweight and had been sick.  My resting heart rate when I started was 109 and I would run for 1 minute and walk for 1 minute and it was torture the entire time. 
I have just kept doing it.  I have cried a few times and thought maybe I was just fooling myself.  Well, I have 1 month before my first tri.  I still struggle with the run and often throw in a walk but my distances have steadily increased and the time running compared to the time walking has increased.  The week before last I was visiting my daughter and I had a hard workout day (you know one of those days when every step seems difficult) and I cried and she said, "I think you can do it mom, I've watched you and seen how much you've improved" and she talked me into doing the entire distance just to see how it went. 
We went to the gym and the pool was closed that day because they were short staffed - oh well, bike and run.  We got on the stationary bikes and I rode 12.24 miles (I am NOT going to mention how long it took..... I am still working on THAT) then went to the treadmill.  I got on and it felt so hard and I barely ran a few steps before walking and just kept pushing myself to run again.  Off and on run/walk/run/walk with my heart rate soaring.  Then between about 1/4-1/2 mile I finally felt my body adjust (my son the runner kept telling me it would happen!) and my heart rate dropped and I was just running.  The couch to sprint plan on here recommends running 8 minutes and walking 2 which I usually do.  I ran for 8 minutes and felt good and thought to myself that I would keep going.  I ran the entire distance with just a little extra 3.39 miles.  I was ecstatic. 
My resting heart rate is now in the low 70's.  I turn 45 on August 15 and that is the day I will do my first triathlon.  I don't anticipate being a ball of fire out there burning up the track but I know I will do it. 
I am long-winded, I know.  All that to say..... just keep pushing.  Push when you don't feel like it.  Just follow the plan.  If you walk, you walk but just keep trying to run as much as you can.  One other thing..... I have done most of my training alone and have found that the few times I have been with somebody I have run faster and farther.  Something about my competitive nature pushes me when others are around. 

I struggled a lot with breathing when I first started running a couple years ago. I would get that same feeling, like I couldn't take a deep breath. It wasn't that I was *out* of breath or panting, but like I couldn't breathe deeply. I think it was more stress than anything, but who knows. Anyway, what helped me was to force myself to breathe at a regular pace. Some people recommend timing your breaths to your footsteps, but I could never manage that. I ended up counting in my head and breathing every every third or fourth count (or something like that, I can't remember the exact count). So I'd count to three, breathe in, count to six, breathe out, and then either repeat or keep counting up. Or sometimes I would time my breathing to the tempo of whatever music I was listening to. I found that after two or three runs doing this my breathing just fell into a natural rhythm and I stopped even thinking about it.

Aside from that, the other poster has the right answer -- stick with it! Follow your plan and you'll keep improving.

all of this is good advice with starting slow so I wont repeat it. you have found a plan and if you stick to it, you will eventually see results if you keep with it. The only thing I will add with breathing is something a lot of people do not realize...How you breath out is just as important as how you breath in. When you breath out do you feel like you are emptying your lungs or just the very top of them? Make sure you are blowing out all the air in there, heck practice it even by tryng to suck your Belly Button into your backbone to breath out. Good luck and stick with it. You will get there!

Lots of good advice on here about breathing- I also started with the couch to 5k program and I've got to say, you'll get better at it and you'll start to enjoy it before too long so hang in there!

When I read your post I got the impression that your girls are bouncing quite a bit and putting some extra pressure on your chest.  I can't stress enough how important it is to have an excellent sports bra if you are endowed at all.  I read an article somewhere (can't remember where, sorry) that if you have bigger than c cups you need to have a bra that separates and supports rather than just squishes.  If you look inside it should look more like a regular bra than a sports bra. 

I noticed recently that Under Armour has a really substantial bra that zips up the front which caught my eye because I always have trouble getting them on and off if they're supportive/tight enough.  It may help you quite a bit if you get those girls properly supported.  They should NOT move when you run (sorry boys!)