Not sure if this is a solution, but I noticed on devices where I had hard coded my DNS servers (4.2.2.1 and 4.2.2.2) that I was having problems. I switched to the opendns servers and no longer have problems on those devices. It might be a coincidence but there could be a problem with Verizon DNS servers.
