If you're trying to construct a stair...is there somewhere for your dwarf to stand while constructing the stair?
They can't construct a stair on the spot they're standing on.
I think they should be able to construct it from above as well as from the side. If there's a down stair or up/down stair directly above the spot you want the new stairs built, then someone could build it from above...but only if there isn't an item in the way or a dwarf standing on the spot that they want to construct it on.
So if you have a dwarf at the bottom of a 1x1 shaft, you'll need to widen the bottom of the shaft to be able to build a stairway, either so your dwarf can stand next to the stair to build it, or so they can get out of the way of whoever else is building it.
Edit: re-reading, I see you say all your miners are stuck at the bottom, which suggests it isn't likely a 1x1 shaft at the bottom...does any one of your miners have masonry enabled? It's possible you chose a rock that's down there with the miners to be used to build the stairway, and that rock won't be reachable by your mason if they're trying to build the stairway from above.
On the other hand, if you're sure you chose a rock that's up above, that your mason can reach...is there a rock that's in the way? The mason won't be able to reach the square that they're building the stairs on in order to move that rock out of the way, so you'd have to dump it and set up a garbage zone down where one of your miners are, so they can dump the rock and get it out of the mason's way.