I just tested the following configurations, please try one of these.
If you already updated to 22.6.3, or some other non-compatible version of the SDK tools and Xamarin.Android, you can either upgrade your Xamarin.Android to match the above setups or download an older version of the SDK tools. Here is how you can do that:
You should make a backup of your
tools folder that we will replace in the Android SDK directory on your computer. Simply rename the folder to something like
tools_backup. That directory is normally installed in a path like this:
Download the version of SDK tools you need from Google using the links provided below.
You can change the version number in the actual URL link to another revision if you need it
Once you download the ZIP, extract the
tools folder and place it in the Android SDK directory above where you backed up the previous version of the
Restart your Visual Studio / Xamarin Studio.
The above steps worked for me on my machine, please comment if something is not working. Thanks for your patience everyone!