"GPS only" location method not working

[AC Question]

I have a Galaxy S4 running Android 4.4.2. I do not use a cellular carrier (i.e., this phone does not have cell service). I have a clear view of the sky.

If I set Settings > More > Location > Mode to "GPS only," I don't get any location information (e.g., in several apps, including US Topo). If I set it to "High accuracy" or "Power saving," I get location info, but only based on the wifi network I am connected to (i.e., it is an approximate location and doesn't have altitude information).

Any ideas why, when Location Services are turned on, I'm not getting a GPS signal?

Thanks!