One does not simply change the conditions of a contract.
They breached the contract by charging the additional fees. A company can't change the terms and say "whoops, that plan didn't work better start charging for small orders."
Uh, it would still be paid? Price increases only apply to new billing cycles, not retroactively, so I don't understand what you're getting at here.
The point is that it's incredibly easy — and relatively standard — to incorporate the possibility of changes into a contract.