While employers are generally not allowed to discriminate on the basis of medical issues, there are exceptions.
The general idea is that there is something called "bona fide occupational qualification", which allows employers to discriminate even based on legally-protected factors. For example, while hiring based on gender is typically illegal, it would be possible for Playboy to run an ad that said "attractive female redheads only", because if they were forced to hire fat bald men to model for their magazines they would be out of business.
I am not sure if this applies to the military in particular, or if other laws exempt the military from standard discrimination laws...but either way, what they did was legal.