I had the issue for many months since installing Mavericks. Since I run High Sierra and Lion where my geolocation is detected instantly and seamlessly, I have the opportunity to compare various network settings between the two and that has just led to the solution of the issue in Mavericks. The problem stemmed from an incorrect proxy parameter value in the network settings pane of System Preferences. Navigate to the pane then follow this path: Advanced-Proxy, then make notice of a value of the Web-Proxy (HTTP) proxy. It should be 127.0.0.1:8228, the numeric strings separated with the colon go to the respective boxes (fields). The parameter itself should be unchecked, no authorization credentials required. Exit the advanced preferences, click on "Apply".
Before changing the value of the proxy I ran the network diagnostics. I came up with the latter spontaneously because "Your geo-location is currently unavailable" message showed up in Lion and after the diagnostics it went away.
I no longer have geolocation problems. I'm not sure whether the following is actually THE true cause of the repeated failures to obtain and locate my Mac in OS X Mavericks (or any other macOS you run), however in my case I run 3 macOSes with 2 of them on a connected external drive Mavericks included. For those I had Spotlight disabled for a long time enabling it only for an internal drive. I don't have explanation why it hit Mavericks but not High Sierra which is also installed on the external drive, but suspect it's due to incorrect indexing of metadata across all of the partitions.
I turned on Spotlight for every partition I boot into turning it off for the other two (e.g., if Mavericks is current then Spotlight disabled for the others). I do it every time I re-boot from one of the 3 partitions. After that Mavericks was able to establish connection with geolocation services and the function is rock solid since then.
Maybe that helps those of you who struggle to get it working. Try running metadata processes by re-indexing your drive and make sure it's the only bootable partition or, if not that Spotlight is turned only for the current bootable partition.
I'd be interested to know if this suggestion rectifies this annoying misbehaviour.
IMPORTANT UPDATE #2
I suddenly started to have this problem in Lion that along the course of 7 years I use it never showed it but managed to reproduce and solve. To make long story short: if the problem can't be cured neither by manipulating proxy settings nor re-indexing the volume the chances are it could arise from a corrupted database cache file in one of lower system-level folders owned by a process named "locationd". The specific file I'm referring to is a database file cache.db. In Lion, there's a folder with the path /private/var/folders/zz/zyxvpxvq6csfxvn_n00000sm00006d/C. Inside the folder, you'll find clients.plist file that contains information about every process and application granted access to the geolocation services and several db files, cache.db included. The problem is that macOS doesn't update it properly if you uninstall an application that had previously used your Mac's geographical position. At the GUI level you see this as a blank icon of the uninstalled application in Security&Privacy settings of System Preferences. Changing the plist alone by deleting corresponding values doesn't lead to the auto-update of the aforementioned
cache.db file but causes the OS to lose tracks of the location, hence "Your location is currently undetermined" message when you're in "Time Zone" section of "Date&Time" settings pane. The solution is to delete the cache.db file too and re-boot (the reboot is important). After that it may take some time for the system to rebuild the cache.db file but now your location becomes detectable and the red pin is positioned correctly. It now lets applications use your location seamlessly.
Beware that all above pertains to Lion. In the newer releases, the location of "locationd" files and folders may be different and so can be the database file names and their count inside the containing folder with a high probability so you have to investigate on your own: e.g., in High Sierra, the folder in question is at /private/var/db/locationd/ and inside there're hidden files with the "dat" prefix in place of cache.db. Use the following command to find the clients.plist file which points to the enclosing folder that you can open to look inside for cache.db or similar types of files. The command is
sudo find -x / -iname *clients\.plist* ! -ipath *yourhomefolder* ! -ipath *applications* ! -ipath *system* -prune
Replace yourhomefolder with the actual name of your home folder.
Filter the output out: you need only those entries that contain clients.plist. Look closely for the folder it's contained in.