I got my VZ Hotspot to connect to xbox live and play (laggy - but I dont think when I did I was on 4g LTE). You may want to look up troubleshooting for other devices using VZ connecting to xbox live.
Can you connect just fine to pc's using your phone with the same PW?
I'll try with my HTC8x phone today and report back.