Recent analysis of closed timelike curves from an information-theoretic perspective has led to contradictory conclusions about their information-processing power. One thing is generally agreed upon, however, which is that if such curves exist, the quantum-like evolution they imply would be nonlinear, but the physical interpretation of such theories is still unclear. It is known that any operationally verifiable instance of a nonlinear, deterministic evolution on some set of pure states makes the density matrix inadequate for representing mixtures of those pure states. We re-cast the problem in the language of operational quantum mechanics, building on previous work to show that the no-signalling requirement leads to a splitting of the equivalence classes of preparation procedures. This leads to the conclusion that any non-linear theory satisfying certain minimal conditions must be regarded as inconsistent unless it contains distinct representations for the two different kinds of mixtures, and incomplete unless it contains a rule for determining the physical preparations associated with each type. We refer to this as the `preparation problem' for nonlinear theories.