Location service not working as expected in iOS 8.3
The way to fix it is to power off the device and then open Apple Maps when it reboots.

That way you can determine if the maps app cannot work or if it's related to a temporary issue to a problem with the third party apps.