Do other GPS apps on the phone work? Particularly Google Maps.
Is the internet connection working? As in, when the phone has to recalculate its position from scratch, it can take several minutes to load the full satellite almanac(s), and a common shortcut is to fetch the almanac(s) via the internet.