I just started a new game with the latest version (I think) 0.19.27. Went to build the compact stairs to build a cellar -- dig out a 2x3 space, build a stair on one side, build a floor under it, dig out the other side, add that staircase and put a floor under it, dig under the floorboards of the first stair, excavate the furthest tile of where the new staircase will go, and the first staircase and the floorboards deconstruc! It used to work. Not seeing anything about it at Steam, either.

Think I'm going to switch to a long multi-level stair. Probably makes more sense anyway, getting cold storage further from buildings.

[EDIT]
Never mind. I restarted my machine and now it works like it used to.
[/EDIT]