check for carrier update? report to verizon's iphone department so they can get it fixed with apple (after u get past generic phone reps saying beta this beta that or whatever else)
VZW's carrier updates have nothing to do with Apple's firmwares, never have - they're plan-specific. I have two iPhone 6 handsets on VZW - one has TMing (iOS9 B3, clean install), the other has it blocked (8.4) - and the Carrier profile number on the former is 20.6.10 and the latter is on 20.0, but the PRL is identical at 15379 (My Air is on 20.1 and my iPad 3 is on 20.5.4). All have UL data and are in a Nationwide Family Plan. There's 3 options to "fix" network related issues, 4 if you include this hand-holding...
The carrier settings are stored on the SIM card, not in Apple's firmwares.
First, ensure you're enabled for SMS so you'll have a back up option to iMessage. Option 1, log out and back in to iMessage - I did after the iOS 9 install (on one iPhone 6 and my iPad 3) - I have had no problems with iMessage since. Next Option, Log out of iMessage then Reset your Network Settings; after the reboot, re-enable iMessage - this worked for my iPhone after installing B2. Last Option, call VZW Tech Support - not CS, they're generally useless sales persons that can't help at all with this - and asked for a "network reset"; I did this just a few weeks ago when I was having problems connecting to VZW's network after a few days in USCC territory - a new Carrier Update came out the next day, and I didn't have a repeat of my network issues when I made the same trip this weekend.
I've never had luck with choosing the Settings>General>About option others have reported about.
Good luck.