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!
What's the address of your DN server as reported by your router. You may want to deconfigure the router as the DN server (same address as the gateway) and put in a manual entry in the settings of the router (if available) using the router settings page. Currently, my DNS Servers are: 184.108.40.206, 220.127.116.11