I don't know if your GPS lock will be fixed by a software upgrade. I'm running stock MR2 and the GPS has, if anything, almost scared me by how FAST I get a lock. Seriously, the GPS gets a lock before Google Maps can load the map based on the cell triangulation location. I've never actually waited any noticeable period for a GPS lock on this phone in the 2+ weeks I've owned it.
I have all three location services turned on (GPS, Verizon, Google). Do you? Check Settings / Location, select everything that can be selected.
Your phone is still under warranty (from what I've heard it's a one-year warranty and the phone came out this year, so everyone's still in warranty). If the GPS has never worked, I'd talk to Verizon about it ASAP.
i know it sucks to lose all your info, but if you haven't rooted, have you tried a complete wipe? Maybe try a RUU to see if something might be corrupt with your radio? When WiFi messed up with my phone after using gingerbread ROMs, I RUU'd back and re-rooted my phone and all is good. FYI, my wifi issues continued on ROMs/Radios flashes after the initial problem.
Itsthe 20th and still nothing.... I cant root this thing because itll be my moms phone when something else comes out that ill like better. I wanna root it so bad but shes afraid it messes stuff up... Trust me ive explained it to her a dozen times, but she likes her stuff stock