As I was tunneling straight down, I accidentally built a down stairway instead of an up/down stairway and now I can't reach any of the lower levels. How do I convert this stairway to an up/down one? I've tried designating an up/down stairway (nothing happens) and building one using b-C-x (error message, could not find path).
Building an up/down stairway using b-C-x, as mentioned in the question, is the correct way to solve this.
If the down stairway was build as a construction, then this would first have to be removed before building an up/down stairway.
However, in this case, it looks like the real problem is that your dwarves can not reach the construction site. My suggestion would be to dig an alternative route to the stairway so that your dwarves could then build the up/down stairway. Of course, this might involve digging a stairway on an adjacent tile, making the original stairway a bit redundant.