What they mean by "nonconstructible" has nothing to do with "nonconstructive". "Constructible" is just one particular set of rules (like "vertex-decomposable" and "shellable") by which a class of finite geometric objects can be built up stepwise.
The thing that's really blowing my mind is that all of these definitions, and any definition even remotely like them --- call one generically "buildable" --- has to admit "nonbuildable spheres", because of that theorem of Novikov that bhudson pointed out that topological-ball-ness of a simplicial complex is not decidable. Because if the buildable things were exactly the balls, then ball-hood would be decidable, because any "buildable"-ish property is decidable, since there's only finitely many orderings (albeit exponentially many) with which you could slap together simplices.
This fact makes me feel even dizzier about my (already hazy) understanding of the relationship between n-category theory and n-dimensional finite geometry. I wanted to believe that a category's n-cells are like little (directed) n-dimensional triangulated (or maybe polytopated, if that's a word) balls. But they can't be, if the criteria for being a category is decidable, which I would hope it would be. Instead they are some special "buildable" variety of (directed) n-ball, one dictated by the rules of categorical composition.
Unless somehow the apparently innocuous insertion of the word "directed" in there somehow makes these undecidable questions decidable for the case of directed topology. But I don't feel lucky enough to hope for that.