I think the situation was vastly different in The Circle.
What was the legitimate government? Was there a legitimate government? Once the Cardassians withdrew they started calling it the "provisional" government. The fighting in The Circle may have been seen by Starfleet as Bajor's way of sorting out the mess and establishing a full-fledged government instead of something provisional.
Which side should they have supported (keep in mind we tv viewers had more information than Starfleet)?
At least in the Klingon civil war there was an established relationship between the Federation and the legitimate Klingon government that went back several years.