They're not legally required to approve any app. Banning Uber's app would not be cause for criminal action, but for a civil suit for damages or breach of contract. The argument might go something like this:

1. Uber's app had previously been approved.

2. Apple, by their previous policies, therefore led Uber to believe that they could build a business around an iOS app. Relying on that information, Uber invested billions of dollars into their business.

3. Apple, by now banning Uber's app, has committed an act that damages Uber.

Also, it would be difficult for Apple to come up with criteria for an acceptable app that would disqualify Uber but not also millions of other apps, without having some new condition specifically aimed at Uber. This could be used as evidence that Apple intended to cause damage to Uber.