Gul Madred more or less stated that the Military came to power during his lifetime.
What Madred really says is that the Military made life better for him. Perhaps that was only
for him personally? That is, perhaps Cardassia has wallowed in misery for the past thousand years, but the Military at least cares for its own, and things would be much worse if the likes of Madred could not enlist and raise their standard of living that way.
Assuming he was the same age as his actor, David Warner, who was about 50 at the time, this would suggest that it happened about 40 years in the past.
But we have examples of Cardassian males who look much younger than their human-equivalent years: Dukat for one hasn't changed a bit between those days depicted in "Wrongs Darker" and those of the main episodes. Madred might well be 120 years old in "Chain of Command" by that standard.