I think a timeskip of at least 100 years, perhaps more, is acceptable to make things different enough that shaking up the peace drastically would not invalidate SC2's ending. I'm trying to think logically of what might happen to the K-sector in a century's time.
Without the threat of war and the charismatic Arcturus or Valerian, the Dominion has weakened as a government. Though it's people remain free and happy, it's heredity rulers, the Mengsk dynasty, have not held the same power their ancestors did. The Dominion now resembles the Confederacy or Earth's democracies more in structure, with de-centralized planetary governments and a ruling council headed by an Emperor Mengsk that holds a veto over their decisions, but not much direct power. Some outlying worlds and renegades resist the government's power simply because they feel confident they will not be disciplined. The Umojan Protectorate has joined the Dominion and the Kel-Morian Combine has become de-centralized, their homeworld of Moria stripmined after decades of plundering and many of their more powerful members seeking new planets to lay claims to.
The Protoss have resettled Aiur. The Nerazim remain united with them, but their nomadic nature means they spend a lot of time away from the planet, unattached to Aiur. Some newborn Protoss, still bearing their nerve cords, have opted to keep them and devote themselves to the Khala. Memories of Amon's corruption still linger in the long-lived race, and the Khalai-adherents are sometimes ostracized and viewed with suspicion by their older brethren. As a military power the Protoss have weakened: they have no enemies to fight, and some of their more battle-hungry warriors abandon the Daelaam to join with the Tal'darim. The Tal'darim, in turn, have begun to suffer ideological differences in the wake of Amon's death and this influx of new warriors that were ones their hated enemies.
The Zerg under Zagara are not the hostile aliens they once were. They keep to Char and nearby planetary systems, growing and mutating. Some Terrans and Protoss, concerned about Zagara's silence, wish to strike and eradicate the Zerg before she becomes hostile, holding her inferior leadership and intelligence from Kerrigan as proof that she will easily fall. Others wish to avoid a war and would leave Zagara to her own devices as long as she remains passive.
And it goes without saying the UED are back.
Anyone else have plot ideas for SC3?