I had the same symptom, and disabling "Bluetooth scanning" in location services resolved it:
http://stackoverflow.com/questions/34414216/using-bluetooth-scanning-for-location-accuracy-android-mhttps://stackoverflow.com/questions/34414216/using-bluetooth-scanning-for-location-accuracy-android-m