I have the same issues. 6+ on Verizon as well. I turn off the cellular connection in settings and turn it back on. Seems to fix it.
Im having this same issue with Verizon, iPhone 6. It seems to be when I leave a Wifi network, Safari doesn't work. I can use apps such as Facebook, but even links inside Facebook don't work. Turning Cellular off and on fixes it for me too. But its frustrating.