I've a rather odd issue since upgrading to iOS 8.1. I did a clean update, I restored my iPhone and didn't restore from backup. I started over, so there should be no residual software issues related to backups. When I first start my iPhone, location services works fine. But within about an hour or so, no apps can find me. I get "Cannot determine location" in apple maps and "unable to locate you" in any other app. This is fixed if I restart my iPhone but again within an hour it starts doing this again. Toggling location services on/off does not fix this. Only completely restarting the iPhone fixes this.