Are you inside or outside when you are initially connecting. from a completely cold start any satellite receiver needs to have at least a reasonable signal quality to get the information on what satellites are in view.

Once it has this initial information it is then able to use much lower satellite signals. If you are inside then try going outside, getting the first lock and then going back inside again.

Does the orange light flash on the unit during these 15 minutes? If so then the unit does have a GPS lock and it is most likely a communication issue between your PDA and the GPS unit.