MS loves "legitimate" Linux
In the case of SUSE, the distributor had a patent license, last I checked; I don't know about the others that are supported, but I have to infer that MS, for whatever reason, does not consider RHEL to be a legitimate product.
To this day, MS has yet to provide details of its patent claims against Linux (broadly defined), yet demands royalties from Android vendors for reasons it doesn't allow said vendors to disclose (and refuses to disclose itself). As long as these practices continue, one can count on myself any many other Linux users to be suspicious. Thus, if Satya Nadella wants to alleviate the mistrust, the best things he could do would be:
1. Offer Brad Smith early retirement and strongly suggest that he take it.
2. Publish all of the patent claims against Linux for all to see and scrutinize.
3. Release the Android vendors currently paying royalties to MS from their NDAs.