I loved my international HOX, so when got dropped in water i said lets go for the ATT HOX+ that has LTE.
Big mistake! I have OP's same issue, im in spain and my provider is Movistar.
I bought it on e-Bay, configured all the APNs, I used settings from their webpage and also tried telephony.db values from an international rom, stock rom didn't tether.
Rooted stock (4.1.2 i think it was) still nothing.
Elegancia (4.2.2) ROM, still nothing.
Changed some stuff on the telephony.db, still nothing
Swapped the wifirouter.apk with the international wifirouter.apk, still nothing.
Nuked TetherGuard.apk, still nothing.
Installed Moto-X tether Xposed module
, still nothing (probably cause it's for android 4.4).
I read that AOSP or Cyanogen ROMs don’t have this issue.
I also read that if you swap telephone.db from international version to USA version the phone goes into a reboot loop, [More Info]
I guess the solution lays in something similar to the Moto-X tether patch, but i don't really have the time to fork the project, and try to get my tethering working.
Hope someone can give us a hand, im sure there are at least 5 more people in this same situation.