Alright, I called Verizon, and the expected happened. They asked me if I was getting a data connection, and if I can connect to the internet. Yes. They asked if 911 or Location was on. Location. They asked me to take the battery out and reinstall. Did it, nothing. Finally, after 32 minutes, she said to reinstall Google Maps, and if that don't work, keep searching forums for a solution.
Not to sound sexist, but the only time I ever hate talking to a female is when I have a tech question. It's no insult, ladies. We're just geekier.
So what do I do? I'm gonna reinstall the ROM update and get back to you guys.