I was having this same problem this evening after doing a fresh install of my favorite ROM. The solution that I found was to turn off Wi-Fi and ensure the phone was connected to a cell tower's data. It seems that when connected to Wi-Fi, the phone tries to use not only the location from that...