In the recent past, I had the issue that I could not run Xamarin.UITests for Android locally on my computer.
This issue drove me crazy for long time, even because in App Center everything was running fine, so I knew my code was good and it had to be some configuration issue.
What didn't help, was that the error message was quite misleading and above all "sometimes" it was indeed working (typically after two or three failed tests, suddenly it started to work for the remaining tests...).

Anyway, after some time, luckily I've found the solution in this Stack Overflow question: if under the C:\Program Files (x86)\Android\android-sdk folder you have both platform-tools and one or more platform-tools.oldxxxx (xxxx are some strange numbers at the end of the folder name), then delete these .oldxxxx folders and you should be finally fine.

Also remember that to run Xamarin.UITests, you must set the following environment variables:

• ANDROID_HOME, typically set to C:\Program Files (x86)\Android\android-sdk
(this is automatically set by Visual Studio)
• JAVA_HOME, typically set to C:\Program Files\Android\jdk\microsoft_dist_openjdk_1.8.0.25
(this is not set by Visual Studio, you have to do it yourself)