work on the breathing part and also on specific workouts that will expand your pulmonary capacity. Also, be sure to warm up adaquately.
First, make sure you are not restricting your airways. A recent article about vocal cord restrictions comes to mind, as does all the online articles about breathing deep with the diaphragm. Look 'em up, try 'em out.
Then running intervals or hill sprints (or both) and the like and you will probably find that when you return to a more usual running pace, it is more effortless and your body has learned efficient ways to accomodate it.
Also, be on the lookout for medical issues like allergies, asthma, COPD, or anything else.