I'm trying to use the Verizon tethering app (and have tethering enabled on my Verizon account). My MacBook sees the hotspot, but does not connect successfully. I'm using WPA mode. The phone sees the Mac, but apparently never issues an IP address.
I resolved this on the Mac by turning wifi off and then back on. On the Win7 PC, running the network troubleshooter (which I believe turned the adapter off and on) also solved the problem. I believe it may be related to some state left over from a previous connection in both cases.
Off-topic: with a 4G (LTE) signal, internet access was comparable (maybe better) to my 6Mb DSL access at home.