hatescam,
It is imperative that you cut off ALL contact with this scammer immediately. No matter how real it seems, it IS a scam. There is absolutely NO doubt about that.
The reason the pictures look real is because they are real. He stole them from a real soldier's facebook page, photo-sharing page, or somewhere else online. He is just pretending to be the person in the photos. He doesn't even know that person--he just copied the photos and is using the name on the uniform. In reality, the person writing to you is almost certainly a young black man from Africa.
The moment a "soldier" asks you to write to the US military and ask for ANYTHING on his behalf--whether it is leave, phone, or something else--he has shown himself to be a scammer. The US military is a VERY self-contained organization. They do not ALLOW civilians to make requests for soldiers. A soldier is responsible for requesting his own leave (and everything else), and those requests are handled internally. Leave is like vacation from your job. He is only eligible for leave if he has earned it--and he does not pay for it (not even for insurance or a refundable deposit). There is no such thing as a special leave to go visit a girlfriend or fiancee (and as afar as the US military is concerned, a woman the soldier met online has absolutely NO connection to him, and is not recognized as a fiancee, beneficiary, or anything else.) Sometimes a scammer will try to tell you that it is a new policy, or a special policy, or that it is because he is in a classified or high-security position. None of this is true, and it NEVER will be true, because it would go against the basic principles of the military's structure.
As Alan said, the money requests typically start with the fake leave request. The "colonel" would respond that leave was granted, but that you have to pay a fee for leave. Sometimes scammers will skip this fee, but inevitably, before the fake soldier can come to see you (which will never actually happen because the scammer has no access to the person in the photos you have been sent), something will come up that requires your money.
Everything connected to this "relationship" is fake. Scammers often use multiple names/characters to make themselves more believable. Often it is the same scammer playing multiple roles, but sometimes it may be a group of scammers working together. The colonel is fake (and is either him under another name or an accomplice). The facebook pages associated with this scam are fake too.
Need to post photos?
http://scamwarners.com/forum/viewtopic.php?f=28&t=3219
Are you a victim of a romance scam? Read
here for advice and FAQ's.