Assuming the usual consistency caveats, the paradox is no longer a theorem of ZF+DC, but its complement isn't either. So in that case the analogue to the fifth postulate is even stronger, as there are both models in which you get the counterintuitive results of unmeasurable sets and those in which you don't, and the axioms are not strong enough to distinguish the two.