The stories I've seen here are fantastic, for the record.
From a D&D perspective, this style of gaming brings up several opportunities and several considerations:
1) Skills become really important, unless the players are fine with their characters being like the hero in "The Perfect Weapon", the not-terribly-bright guy who goes around believing what each important person says and beating the tar out of people, only to later realize that he was lied to and pointed at people's political enemies. In this game, the wizard and fighter are only useful once initiative gets rolling, and that's an endgame kind of scenario. In this game, the rogue and the bard are the two powerhouse classes, the former because of his insane number of skill points and the latter because he's almost as skilled and can, at high levels, cast a spell that alters people's memories.
(My happy happy joy moment as a DM was getting a secret society of paladins to attack the duke because evil monsters that were essentially high-level bards that looked like cockroaches had used Modify Memory on a bunch of peasants in coordinated fashion to make many people remember seeing the duke committing horrific atrocities.)
So, short version: Skills very important. Some players are going to complain that their character is useless because they don't have enough skill points or helpful class skills. This is either a sign that they're playing a character concept that isn't good for this campaign, or a sign that the campaign needs a few more endgame notes for them to feel happy blowing stuff up while the party bard/rogue takes care of the political stuff.
2) More complex skill checks or more innovative use of skill checks can be helpful. As a DM, you really want to have Bluff and Sense Motive nailed down in terms of definitions before you go, here. By the core rules and FAQ, you don't Bluff every time you lie -- a Bluff is an attempt to manipulate someone into following a course of action you desire. It can be made up of several totally truthful statements. A Sense Motive check can determine someone's general personality and can oppose a Bluff check, but it is not a lie detector and should not be used as one, especially in campaigns like this. (Exception: In d20 Modern, the Investigator gets a class ability that lets him turn Sense Motive into a lie detector -- which, to my mind, serves as evidence that it shouldn't ordinarily work like this.)
Unearthed Arcana has some ideas for more complex skill checks, and they're worth looking at. If the DM wants people without Sense Motive or Bluff to feel useful, he can allow things like:
-Using Diplomacy to improve someone's attitude, and then letting the bluffer take over from there. (Good for Clerics and even Paladins, sometimes, who have Diplomacy)
-Using Knowledge skills in place of Sense Motive in some limited cases, to find holes in somebody's story ("He said that he survived his journey in the desert by finding oases, but I've been in that desert, and all the water holes are too salty to drink -- you only survive that desert by cutting off the tops of cactuses. This man was never in that desert.")
-Remembering to let observational skills like Spot and Listen come in handy -- it's nice for the burly ranger that nobody takes seriously in court to feel useful by overhearing a frank conversation between the bad guy and a henchman.
-Allowing other ability scores to modify certain rolls in certain situations, like using Intelligence to modify a Diplomacy check when the Wizard has had ample time to prepare his statement, or using Dexterity to modify a Bluff check when the Ranger is pretending to be badly injured from a rival group's attack.
3) Magic has to be handled carefully. The DM has to decide whether he's going to limit divination spells in his campaign (ie, change the game-world), arbitrarily declare that the bad guy has a plot device that stops divinations from working against him (the Baldur's Gate approach), or use in-game spell mechanics to make the bad guy impervious or well-defended against such divinations (ie, a ring of mind blank or a convoluted-enough plot that asking "Who is the evil culprit" produces an "everybody" answer). In this game, a potion of glibness can be absurdly overpowered as magical items go, and social skill-boosting magical items, while tempting to help out the party Fighter or Wizard, will inevitably find their way into the hands of the rogue and bard, who will then get seriously powerful.
4) Monsters can and should be altered to make use of the intrigue. Skills can and should be swapped out liberally for this world, unless you want the monster to be a force that is acted upon rather than a force that acts upon others. At least in 3.0, there were many outsiders with impressive combat abilities but lousy social skills. In 3.5, a lot of this is corrected, but look at those changes and consider applying them to any creature that you want to be a vital schemer in the big game.
Anyway, not much to add to the story angle -- again, this is marvelous stuff. Just make sure that your players are either ready to play, content to wander around killing whoever their leader tells them to kill, or comfortable being uncomfortable. When I sprang political intrigue on my players after many simple sessions, they got frustrated.
Also, as a DM, you should consider whether you should let the PCs reliably trust anyone. My players got frustrated when they felt that they couldn't trust anybody -- even Mulder and Scully had Skinner to back them up, and just about every time he seemed to be against them, he still had their best interests at heart.
. 
