"[In Star Trek VI] the depletion of [oxygen] from Qo'nos, a single planet, meant the practical extermination of Klingon race and death of their Empire."
For kicks, let's give the 23rd Century Klingon Empire half-a-million ships (military, civilian, et al.). Let's assume that each ship can carry an average of, say, 500 people. And, finally, assume a one-month average round trip to the various suitable planets in the Empire (which as of the 2260's was said to have many poor systems, which was the basis of their expansionism).
That's 250,000,000 people per month. At that rate, evacuating modern-day Earth would take two years and two months (assuming 6.5 billion people). However, that wouldn't even begin to account for material, supplies, population growth during evac (we're going to hit 7 billion by 2012), et cetera.
And while that's going on, do you really think the Klingons could do much in the way of their interstellar policies?
Now, chatter from the Federation president in ST6 made reference to completing the evacuation of Q'onoS within a fifty-year timespan, which eases things quite a bit. Let's assume there are just 10 billion Klingons on the homeworld, and that over the course of fifty years the total number to evacuate will be 20 billion. (That's a rough ballpark figure, meant to account for births per year and the notion that older Klingons might just choose to stay and die on the homeworld. We're at 130 million births per year, so I adjusted theirs to 200 million/year in keeping with the 10 billion total. That would give us 10 billion new Klingons within fifty years. (Since the birth rate would decline over the course of the fifty years I was going to drop the total evac population to 15 billion. However, they probably have shorter generations than we do and yet also have far longer lifespans, so more of the original ten billion would be around than is the case with mankind.)
To evac all of them in fifty years (600 months) will require an average rate of over 33 million people per month. Even at fifteen thousand people per ship -- equal to what the Galaxy Class could carry, and it'll have to be the average per ship -- that's still going to require 2,223 ships engaged in constant evacuation with a one-month turnaround time. If the round trip turnaround time were two months then 4,445 ships would be needed.
Of course, Klingon ships are generally not Galaxy-esque luxury liners. Like the Intrepid Class, they are built more for combat performance. The Intrepid Class starship Voyager, despite being on the large side, could evac an absolute maximum of 475 people. A particular type of Klingon civilian transport in the 2370's carried just 441. Thus it might make more sense to bring down the average from the Galaxy maximum to something more reasonable . . . say, an average of 1000. That would mean that 33,334 ships would have to be making trips with an average one-month turnaround time, or 66,667 ships with an average two-month turnaround time. And again, that's just people and not materiel, supplies, mementos, cultural icons, et cetera.
Remember, though, that common estimates of fleet strength in the 2370's are around 10,000 ships each for the Federation, Klingons, and Romulans. While I'm sure there are many, many more private/commercial/cargo ships, there's just no way one can assume that the Klingons are going to be able to maintain their empire without incident.
In short, the depletion of the Klingon homeworld's ozone layer and the end of free oxygen would've meant that the planet would've died within 50 years assuming no one left. However, to evacuate the planet would require thousands of ships times decades.
Either way you're talking about an incredible blow to the Klingon Empire. The fact that the 24th Century Trek seems to suggest that some sort of magic fix was accomplished doesn't negate the fact that the Klingon Empire had to have basically been in a state of reconstruction for much of the late-23rd and early-24th Century.