I came across this thread by a google search. So I many not have the same phone as you all.
I have the Xv6800 with the Valhalla GPS server.
My GPS hasn't been working for the past two days.
I have found in other forums that this is quite widespread for the last two days.
I'm picking up some faint chatter that the GPS goes through a server (at Verizon?) and that is now being blocked or down and not working.
It's called aGPS.
http://en.wikipedia.org/wiki/GPS_Phone
I'm hoping to find more details as more people realize it's not their phone.
MSD