I had a similar problem with Vodafone Italy. Tethering is forbidden with a lot of its data plans (included mine) but ,when I had my Gnex with stock 4.2.2 , I always used it without any issue. Then, from a day to another, my tethering stopped to work using the same firmware and witout touching anything on the phone. Same situation with stock 4.3 or PA 3.95.
My solution ?
https://play.google.com/store/apps/details?id=com.tetherunlocker&hl=en . I used it since I had issues and it permits me to continue to use tethering also with PA 3.95 . Give it a try (to unlock the tethering you have to use it every time you reboot your phone).
---------- Post added at 09:29 AM ---------- Previous post was at 09:22 AM ----------
Last Saturday I flashed PA 3.95 but after 24 hours I noticed a very poor performance of the battery , especially during deep sleep. I installed Cpu Spy and Wakelock detector but I didn't noticed any strange behavior (but I hadn't any reboot). So yesterday afternoon i installed Fancy kernel (r37 "simple version") and now I can say that my battery drain is fixed (with same PA setting, wallpapers, apps and so on...). The battery is ok and the consumption in deep sleep is very very low now
PS: At the moment I have no issues (I enabled also CAB in the kernel) but in the past pages I read that using other kernels with PA 3.95 can cause any issue. Is it true ? In case what I should check ?