Tried the fix above to no avail on my verizon vx6800. With my luck I noticed it was not workign the other day when I was lost in downtown Detroit. Makes me hate that city even more than I did before. I will keep looking online for solutions and get back if I find anything. Stupid verizon, get on the bandwagon and just enable GPS already.

EDIT: After a couple soft resets and getting outside of my office building it is working again. Actually getting more satellites than usual. Thanks for the reg fix above, worked great! Let's hope it lasts!