Same phone, same problem.
I tried everything I could think of:
Restarted phone
Disabled Wifi Scanning in Location Services/Scan Settings
Disabled location
Disabled Google and Google News from the authorized apps, I couldn't disable play services though
Made location use only GPS
I hope...