For GPS to lock on, you need to be outside with a clear view of the sky. This is especially important if it is the initial connection or if it has been longer than 7 days since the last connection. The device has to download the ephemeris tables so it knows where in the sky to look. That can take a while. Then it has to find the satellites which can also take several minutes. You need at least 3 good sats to get a good position. Loacating yourself on the map as close as possible also helps. I have seen it take upwards of 10 minutes before you get a "fix".
You might try using GoogleMaps and clink current location to help speed the process. Google uses cell towers to triangulate and figure out where you are in lieu of GPS.