I think that maybe your approach to realm rulership is the key to this one.  Without pre-judging how successful that was, I find that a lot of hand-waving, eyebrow raising and concerned peering does as well as a heavily-systemed approach for social interactions unless you go to a system (like Burning Wheel or Dogs in the Vineyard) that takes such things **really** as seriously as combat.  

Now - I'm not advocating ignoring social stats/skills/traits etc but rather stepping back from pure rolling-for-success to a more abstract low-system approach of taking them into consideration when your NPCs interpret what the PCs say and do.