When a GPS is first powered up it spits out NMEA sentences but it won't have a lock on any satellites yet. It needs at least 3 and this will take a few minutes to happen. You will know that it has a lock when this:
changes to something like this:
It will happen eventually if you have a clear view of the sky but it may take several minutes. Just walk away from it and check back after about 10 minutes. Assuming you always have the GPS hooked to power and you just put it into sleep mode when not using it, subsequent activations should take less than a minute to get a valid fix.