How can take-off slots suddenly become available even when airspace is congested?
It's a very credible explanation.

Slots to allocate scarce ATC and airport resources are created based on a known rate at which the airport/airspace can handle traffic, and they are apportioned out based on things like when the flightplans are filed, allowing for time enroute and expected arrival times.  (This is a little general -- trying to give a big picture without getting mired in too many specifics of EDCT's, Ground Delay Programs, and so forth -- some of those details can be found in answers to this question.)  When total demand is below capacity, it's common to be told to "contact Clearance Delivery 5 minutes prior to Push for your wheels up time to XYZ," and then on calling Clearance, you're either given a wheels-up time in about 15-20 minutes (i.e. push on time, taxi out, and take off with no delays) or even "released with no restrictions."

However, when demand is greater than capacity (most common when a bottle-neck is caused by something like bad weather at the destination reducing the allowable arrival rate, although also caused when a runway or an approach is unusable for some length of time), then things start to slow down, and you may be given a wheels up time farther off in the future.

Better to sit at the gate not burning gas than burning gas at idle out on a taxiway, or burning a LOT of gas holding in the air, but not most flyers' idea of a good time.

When things are HIGHLY saturated, as it sounds like the OP's scenario, you can't get your slot time issued until you are actually ready to go, but you (or your dispatcher) may have a sense for what sort of delay is likely.  In these cases, you often can see where some aircraft have been given a significant delay, and anticipate something similar -- but you don't actually know what you'll get until you call.

Sounds like the crew for the OP's flight anticipated that they MIGHT be pretty far back in line, and explained things accordingly, but when they actually called then either conditions had improved, OR a particular slot was available (perhaps another flight had cancelled or been delayed) and they got it.  That's not all that uncommon -- you call for your time, hoping for the best &amp; prepared for the worst, and sometimes you get the "wheels-up" time 90 minutes out, and sometimes you get "can you be wheels up in 12 minutes?" and if the answer's "yes" then there's a quick high-five in the cockpit and "tell 'em to shut the door, we're going!"

Due to the lead times involved, when a slot opens up like this, ATC typically does NOT call every flight "in the queue" to shift everybody forward by 5 minutes; that slot either gets used by somebody, or it's just unfilled.  But when we've told our passengers "you can get off the airplane, be back by X so we can leave," making adjustments to that X time isn't practical, so for us that time is pretty well set.  Somebody else who IS boarded up &amp; ready may get that fallout slot ahead of us, and when he does, good for him.