HHaving pretty much the same problem as everyone else here. Took it to the Genius Bar. No luck. I explained to the "tech support" employee what Ive done (hard reset, turned location services off and on, and reset network settings). After I explained that i was having the same problem with multiple apps to include google maps and apple's maps and waze, she still insisted that I delete and reinstall google maps. I did. Same results. Asked if she had anyone come in before w this problem, she said no. we hooked up to the apple store wifi to run a diagnostic. found nothing wrong. Tried maps again while connected to their wifi. And as expected, it showed my location accurately. She seemed to think that fixed the problem even after I explained to her that of course it will show an accurate location since it was using the wifi to find me. she didn't understand and took that as the LTE as being the problem since the location services found me accurately while connected to the wifi...
then she blamed it on my lack of memory storage on my phone. Even after I deleted a bunch of apps and photos clearing about 1G of memory w the same results.
also, she noted that I kept getting kicked off their wifi as the "LTE" symbol kept popping up intermittently while being connected to their wifi. "Oh but that's not what you came here for, but that is odd."
i then explained to her that Ive heard a lot of people were having the same problem with iOS 9.3.1 and when I suggested that it may bet he iOS she said "no ios 9.3.0 had that problem and that's why they came out w ios 9.3.1." So that tells me she has heard of this problem. Contrary to what she said earlier. she kept going back to trying to blame ATT and the LTE. I gave up trying to get her to understand. Asked her if she's heard if 9.3.2 was coming out soon but she said they haven't announced that yet. Great. Yet I'm hearing that there's a beta version out at the moment.
Long short I was sent on my way w a new SIM card that I had to activate and install myself and promised that it would most likely fix my problem. I activated and installed it. Nope. Same problem. Seriously Apple, these "techs" are suppose to be knowledgeable in their trade. Only thing that was achieved today was my loss in confidence in apple support.