Gul Madred more or less stated that the Military came to power during his lifetime. 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.
That doesn't really match up with the timeline, it seems like Cardassia was controlled by the military dictatorship when they annexed Bajor, a process that began in 2318. It seems unlikely that when Cardassia was "peaceful and spiritual" they would not start annexing world with the purpose of stealing their resources.
I think Madred was talking about the accomplishments in a historical sense, those reforms and programs the military regime instituted could have been either recent or historical.
Also it is possible, even likely, that despite the military regime's efforts, there is still a lot of poverty in Cardassia and Madred grew up as a poor youth after the military took power.