We have had customers report the same issue and we asked some phones back to check it out, they all worked here without any trouble… You will most likely need to put your foot down and ask (demand) your provider to allow the phone to use hotspot connectivity.
I have no clue how they can see that you are using your phone as a hotspot, but I guess it could be done with packet sniffing or such (which should be illegal afaik.)
We had one customer who demanded their provider for an explanation and then they fixed (allowed) it. 