How strong is your network signal? What setting do you have location settings on? If it's on device only, it'll take longer than if you had it set to high accuracy.
Yes, I am on Kit Kat, but you should still have something that lets you change what has access to your location. Go to settings > personal > location and see if there's an option for the GPS there.