Besides the increase in roles for members of a Kingdom and the restrictions to be put in place to stop VP giveaways, I would like to re-mention something that I suggested some while ago in yet another thread at the start of the Alliance change:
Limit the size of Kingdoms. If you couldn't go over a certain number of people in a Kingdom, then some of the dodgy diplomacies would no longer happen. Limiting size would increase the number of Kingdoms, which would encourage aggression. The only possible downside I can see is that weaker players may be booted out to make way for stronger, but I would argue that this will push players to be more active (and spend gold, eh Travian?).
Make it so.