I had a similar problem as explained below.
Here a solution that worked for me:
1) delete the one package appearing in the screen shot below.
Nota bene: At this stage VS 2015 greyed out the Android SDK manager buttons, even after a restart.
2) download installer_r24.4.1-windows.exe for windows https://developer.android.com/studio/index.html
3) launch the Android SDK Manager outside of VS and install the proposed 19 packages. This time I could go through the installation.
4) Launch VS 2015 and create Xamarin Android project. Launching Main.axml would launch the designer properly on an android project.
The bug I had
I had the same problem here on a fresh install of Win10 + Full visual studio community 2015 update 3 + .Net Core + Azure SDK and Xamarin. Creating a new project Xamarin Native (iOs + Androird) shows up the same message as mentioned by MikeJ. In addition, running in debug F5 makes the designer have a new popup

Problem seems to appear also here
https://bugzilla.xamarin.com/show_bug.cgi?id=44374
and here
https://forums.xamarin.com/discussion/77669/how-do-i-fix-this-error-the-installed-android-sdk-is-too-old-version-25-1-3-or-newer-is-required
.
Opening the Android Manager does not show up version 25 as an option, instead it shows this

However, we cannot install (greyed out button even by accepting license)

Updating Xamarin did not work neither How to update Xamarin for Android within Visual Studio Community 2015
Some guidance would be great to understand what happened.