From my new Samsung 4G hotspot, the Verizon DNS servers are very slow to respond to requests - or never do at all. Unfortunately Verizon also blocks access to other DNS servers, so there's no workaround.
Verizon: Get yours working with decent & reliable performance, or remove the block.
Added: It's a server issue because the DNS lookups for Verizon's own websites are also delayed!
