Please try one of these configurations, as John Miller pointed here
Windows / Visual Studio 2013 / Xamarin Studio
Xamarin.Android 4.12.02001 using Android SDK Tools 22.6
Xamarin.Android 4.12.03003 using Android SDK Tools 22.6.2
Xamarin for VS 1.12 (Alpha) using Android SDK Tools 22.6.2
How do I downgrade my Android SDK Tools?
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:
C:\Users{USER NAME}\AppData\Local\Android\android-sdk\tools
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 tools folder.
Restart your Visual Studio / Xamarin Studio.
EDIT:
Xamarin Studio 4.2.5 has resolved the issue. It needs Android SDK Tools 22.6.3.