I had the same experience. When I went from the older Verizon router (red front panel) to the latest "wedge shaped" masterpiece from Verizon, I finally was able to connect. I had previously tried three other routers, including the older Verizon router.
IMO, it simply shouldn't be this hard to connect to the WiFi box!