I am having the same problem - Verizon recently sent me a new (refurbished) handset to correct a problem with a weak signal. My old DINC did not have this problem, but the new one (used for about a week now) is taking a long time to find the GPS.
P.S. Running stock.