У меня есть эта проблема с моим эмулятором, я использую API 5.1.1, и у меня есть последняя версия Служб Google Play от диспетчера SDK.
AndroidManifest.xml:
<uses-permission android:name="android.permission.ACCESS_FINE_LOCATION" />
В build.grable:
compile 'com.google.android.gms:play-services:+'