I feel everyone's pain of no longer being able to tether your phone to pc. I too have experienced the same thing on my Motorola RAZR after they updated it. I have been able to tether ever since I got my phone a little over a year ago. Now, they want me to pay an extra $29.99 per month in order to tether!
I think they can charge as long as you have an unlimited data plan. It only make sense because otherwise people's data usage would be way over the top. However, for those of us who do not have an unlimited plan, say for example you pay $30 for 2 gigabytes of data per month, I'm not sure if they can charge a tethering fee in that case. At least that's what I was told by the FCC today when I filed a complaint about this issue.
What pisses me off is I see no difference in whether I use my phone or my computer, via USB tethering, to access the Internet using my 2 GB of data per month which I pay for.
I called Verizon yesterday and was told that I could get a plan which included 6 GB of data a month for about the same price I am paying now. Umm, yeah, like I want to get stuck in another two year contract with them. I am counting the days now until my contract expires early next year. I'd rather go back to my old TracPhone than stay with them.
Please keep us updated about your complain. I too was of the understanding they could not charge a separate tethering /hot spot fee if you were on a tiered data plan.