if you'd posted in the military forum I would have gotten to this sooner. I'm a military (army) residency, military (army) fellowship trained pediatric subspecialist-- but know plenty of people who did military residency, paid off their obligation, then did a civilian fellowship. in my experience, those people who have done the payback as gen peds then apply civilian do very well-- in fact maybe better- than those that go straight through for a few reasons.
1) you will have 4 years of gen peds under your belt, which gives you a perspective those that go straight through don't have. you've been in the trenches, and this counts for something.
2) along with #1, you likely due to the military's system will have had some experience in a leadership position-- chief of inpatient peds, newborn medicine, the department, etc. also looked on favorably as this reflects your leadership and time management skills which many civilians won't have had that early in their career.
3) if you deploy or do other operational things, this gives you interesting things to talk about during your interview that will make you stand out among your peers. you'd be surprised at the number of former military folks out there, and even if not directly peds related this shows you can handle some stress in your life. your perspective on what is stressful definitely changes after deployments.
4) you can use your post 9/11 GI bill during civilian fellowship to help defray the pay cut you will experience going from attending to fellow. I'm not sure on exact amount and it varies on location, but this can be 1500-2300K per month. Google "BAH calculator" and put in the ZIP code for where you are looking and you would get the E5 w/ dependents rate.
http://www.benefits.va.gov/gibill/docs/pamphlets/ch33_pamphlet.pdf
downside-- research is not an emphasis in the military. so if a program wants to see a lot of research/publications, that will be hard to do. however, even the most high powered programs I think will give you a bit of an out if you come from a clinical heavy background.
if you decide you want to do a fellowship while in the military, that's doable as well. however as people have noted, it depends on the needs of the military service you are in. for example, if they have plenty of peds pulm they aren't going to train any. if they need peds GI they may train 2-3 in a given year. it really varies year to year. the only specialty that always get approval is NICU (since so many of them leave once their obligation is up there's a constant need to train more) and to a lesser degree developmental (due to constant demand for more).
good luck!
--your friendly neighborhood either way fellowship is the way to go caveman