It doesn't apply to Google Maps Navigation AFAIK but you should ask this specific question to your local Verizon dealer.
For instance, I know of examples where Motorola Droid and HTC Droid Incredible users each utilized Google Maps Navigation with a Verizon contract (but again, be sure to ask before you buy the phone).