Ok so I upgraded to the OS version that was on Verizon's website, and I can use the GPS with the BBMaps now.
The GPS works with the BBMaps, but not GoogleMaps... But I think that Verizon still has blocked that so no big deal.
Just went and tested it, and it worked EXTREMELY well, so I must say that Verizon is now off my shit list. Congratulations to them.