Yeah, evidently some users are not noticing the announcement PSA: Make sure to select a category for your new topics! which warns of this.
With my not wanting to reproduce the problem experimentally myself, I'll have to ask - If someone composes an original post without a category, then presses the + Create Topic button to submit it, are they seeing the "Oops! That page doesn’t exist or is private." page immediately, or do they see their submission intact once, and then only thereafter are unable to see it again?