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-m