GPS doesn't work in AGPS mode

Hello. I created a GPS application for Android using standart Input.Location method from http://docs.unity3d.com/ScriptReference/LocationService.Start.html with desiredAccuracyInMeters = 10, updateDistanceInMeters = 2. My app is now installed on hundreds of devices and it turns out that on some of them data I get is very inaccurate (accuracy is about 500 meters). When I run GPS Test app (from Google Play) on the those devices, it tells me that GPS signal is fine and accuracy should be about 10 feet. Google maps's coordinates seem to be very precise too. If I switch geoloacation mode from AGPS (default) to GPS only in my device settings and launch my app, I get the correct data (but it's less accurate then on devices where my app works fine with AGPS) All tests I take into consideration are carried in the same conditions. Any ideas?