The TOS is a contract. The contents of a contract are not law, but the fact you signed the contract and agreed to abide by that contract is law. And by tethering without the tethering plan, you are in breach of contract which is illegal.
People should be lucky that AT&T is just warning you then moving you to a tethering plan if you continue tethering, they probably do have grounds to take you to court for theft of service.
I would disagree with having "to abide by that contract is law." The courts/judges/legal system would have to decide on this part (ie, whether the TOS are fair and justified and whether violating them is against the law), just like when Apple thought that jailbreaking their iPhone was against the TOS and thus against the law. As we know, the courts decided otherwise. So it is not clear-cut as some people like to think.
Hence, consumers should not willingly accept every TOS that is put in front of them as a holy grail law. If all people accepted Apple's TOS, jailbreaking your iphone would still be illegal according to Apple. Consumers need to actively protect their rights because business will not do it.