But are you on tethered data? There's a difference between unlimited data from the phone and data from other devices going through the phone. This definitely looks like an AT&T issue (and they'll probably tell you the same thing - that you have to pay for tethered data [it actually makes no difference, but it's another way to get another dime from you]).
I can confirm unequivocally that FoxFi works without issue on a Verizon UDP. Sorry, I know that's basically not value added for you, but others need to know!