Companies should be able to hire/fire based on their preferences. That is the benefit of being privately owned. Forcing them to keep this employee on their payroll when she is not conforming to their standards would be just as bad as being forced to hire someone who did not portray the image that they wanted (ie visible piercings/tattoos/strange hair colors, etc.).
Private ownership means squat when it comes to affirmative action.
They didn't have the policy for twenty years.