Yeah, people like to whine about how Kings are OP. They really aren't, though.
What is OP is anything stacked - Admirals especially, but also Tycoons, Engineers, Generals, Sentries, whatever, and yes, including Kings. Any specialist that can be stacked can turn in to a real nightmare if it isn't dealt with correctly.
That said, like Silver said, though indirectly, the best way to fight Kings isn't with drillers. Kings boost the efficiency of the player's drillers; unless you have kings as well, you drillers will be weaker. To counter this, non-driller fights are to your advantage: double agents, martyrs, saboteurs, sentries, generals, and shields. Speed also helps, as it always does.
Another thing to remember is that the first king promotion is very weak; though the drillers get a significant boost, the loss of all shields makes them vulnerable. It is often best to just go ahead and hit them early, because you can assume that if they have one king, they are going to try to get more.
Good luck out there.
"No man chooses evil because it is evil; he only mistakes it for happiness, the good he seeks."
-- Mary Wollstonecraft