I do believe the GPS is supposed to be working on the Verizon Tour. I know that Google Maps and GPS on the Sprint Tour don't work together at all. Hopefully there is a fix soon. Have you tried a battery-pull? What version number of Google Maps have you downloaded?
I just had a very similar problem. My GPS was spot on last night. I plugged it in all night to charge it, went to work this morning and all of a sudden the GPS wouldn't work for anything... Gmaps, BBWeater, GPSed... nothing. I just did a battery pull based on reading this thread, restarted the phone, opened Gmaps, and boom straight to my location within "8 meters" though it's probably within 1 really. WTF!?