Just anopther point. Many people do lose weight and get fit in basic training, and to a degree, there's allowance for that.
However, training (non-physical) starts from day one. While the basic training group can handle some people falling behind due to physical issues, as that percentage grows it reduces the time training in actual military techniques. THis means more troops missing out on some training or getting shorter versions of training, or longer hours, both of which mean higher costs overall per soldier.
Of course, they could set up a "pre-basic", as someone mentioned, that was specifically focus on physical fitness and/or weight loss...but again, you increase training times, which means a higher cost per soldier.
Already, the Army spends something like $150,000 to $250,000 per soldier to get them through basic training and AIT (tech school/job school). I'll have to double-check those figures, because it's been a while and they could very well be different now.
There's also an issue with obesity IN the Army (I can't speak so much fo rother branches of service). There are weight and height standards, as well as physical fitness standards. However, the Army has been so short on personnel, especially trained personnel (thanks in part to all the early retirement incentives offered during the Clinton era) that many people are given waivers to stay in. In almost every Army unit I've been in there have been people who have not passed a PT test in over a year, and some for several years (they're supposed to be given every 6 months). Same with weigh-ins.