I have the same problem here, but mine seems a little different from what all you guys keep saying.
I have the HTC One S and everything has been working perfect up until yesterday. I was on a road trip and everything was working perfect location wise. My weather apps updated like normal, my Google Now was working fine. Was even suggesting places to eat in the city I was visiting. - On my way back home after my trip it randomly told me to turn location services on. Ever since then, it has been telling me that Location Service is Off.
The difference here, all of my actual location apps such as Maps, Now, Facebook, etc. are actually working normally. I'm getting local updates, everything is posting the right way. Not getting any error messages in any other apps to enable location services except fro Google Now.
But even when I go into Google Now, it still brings up a card that has the weather for my city, and then under it there is an additional card that says Location service is off - but when I tap on show more cards it brings up everything else as normal. Drive time to work, drive time to home, drive time to the bar I visit frequently, nearby events, and related searches that I've done lately.
Everything seems to be working perfectly - but I just can't get the card to go away that says my Location service is off.
The only other minor detail is that on my home screen on my weather clock, where it usually says my city is now showing "Current Location" instead of my city.
Other than those tiny problems, it seems everything is working fine. It's just a simple irritating fluke that I can't seem to fix, and all you guys are ballsy as hell because there is no way on earth I am factory resetting my phone. T-Mobile tried to get me to do that earlier today and I was like, you're on crack!