Hmm...
Okay, lets say that under the peace treaty the Federation/Grand Alliance is allowed to establish a base in the Gamma Quadrant, for exploration missions support and such.
Okay, the base is currently under construction, its a joint Federation-Klingon project (the Romulans had originally intended to join the project but pulled out without giving a good excuse).
Anyway, contact with the construction crew is lost and so Starfleet orders the ship to investigate and they arrive to find that base had been destroyed. Among the dead is a relative of a powerful Klingon clan chief who assigns his nephew, a rough warrior of the old school, to "assist" and he arrives with his fully armed and ready Klingon cruiser eager to beat some answers out of somebody. His first stop is the Dominion's homeworld believing that the Dominion is responsible. The PCs of course go along to prevent a "diplomatic incident".
They arrive to find the Dominion in an uproar. Jem'Hadar ships fill the skies all of them with their hackles up ready to blast anything that wanders into their area.
Odo shows up and informs the PCs about the troubles he's been facing. Bushfire revolts have broken out throughout the Dominion. Even a number of Vorta commanders have borken their conditioning and led their own Jem'Hadar into active revolt. The worst of the matter is that the various "liberation" groups have formed an alliance and began joint operations and the Jem'Hadar are hard pressed to keep the lid on the situation. Apparently some liberation groups have also began targeting Alpha Quadrant assets and ships on the principle that they are just another "Dominion" here to plunder the Gamma Quadrant.
[Side note: there is a Romulan Tal'Shiar operation going on in the Gamma Quadrant. They have began sending "advisors" and ships to assist the liberation groups and in fact the whole unity of the various liberation groups was started by and controlled by the Tal'Shiar. They want a destabalized Gamma Quadrant ripe for their own expansion...
)
Well take it from there Zymmer, this is all off the top of my head so its all you get for the moment
Arise, arise, Riders of Theoden!
Fell deed awake: fire and slaughter!
Spear shall be shaken, shields be splintered,
a sword-day, a red-day, ere the sun rises!
Ride now, ride now! Ride to Gondor!
Theoden King: The Return of the King