Try going to General>Restrictions>Location Services and set to Allow Changes. If that, for whatever reason, doesn't work then you can try resetting all settings in the settings menu though that's a bit bothersome. Also, certain routers will cause it to not work right as well so if you're connected to WiFi then disconnect.
In addition to the expert advice from Chris make sure you try both ways meaning off WIFI. Reboot and I hate to say this because it seems like the most given out advice to fix everything...LOL but you might have to to restore your phone as new and start over again. Hope you work it out and good luck.