Evasion generally has to do with mandatory liabilities and provisions. For example - tax avoidance and evasion. It's legal to plan your activities to avoid incurring a tax. It's illegal to take an action that results in a tax liability and then not pay it or attempt to hide it.
For me, what Uber did is akin to avoiding roads that are known speed traps. Yes, Uber is required to obey the laws of the jurisdiction they are in, but they are also able to deny service to anyone for any reason so long as that reason does not fall under a protected class (age, race, gender, etc.). Refusing service for being a suspected member of law enforcement is allowed. Just as certain small businesses provide discounts to law enforcement in appreciation of their service, others can refuse to serve them.
The issue of whether or not what Uber did was illegal seems to hinge upon whether or not the underlying activity was illegal. It sounds to me (and has been stated elsewhere) that many of the jurisdictions where this was being used have unclear or incomplete ride-sharing and booking laws. This would make the activities by Uber up for legal debate, just like the Uber legal battle in CA on whether to classify drivers as employees or contractors. If there's not a consensus or existing legal precedent that a specific activity is illegal, you can't say that their activity is evasion because the activity they are trying to "hide" hasn't been ruled in court to actually be illegal because this situation is still relatively new and hasn't been adjudicated on yet. Once we have a decision by the courts on the underlying activity, then yes, using Greyball to avoid authorities would be illegal.