This is a common misconception avoidable by a more careful mathematical description of what's called a "quantum state". BTW for many examples of sloppyness I never understood the hype about Hawking's famous "Brief History of Time", but that's another issue.
Usually students are instroduced to the concept of quantum states using the "wave-mechanics apparoach", which is indeed a good way to heuristically introduce modern quantum mechanics, but it's not the best. A better way is to use "canonical quantization", which to a certain extent is also pretty hand-waving and can be misleading, but it's a better heuristic way to introduce quantum theory, because it is not referring to a certain representation (for wave mechanics that's the position representation) but already in the very beginning start from the abstract Hilbert-space formalism, which of course also has its disadvantages from the didactics point of view. I think a "healthy mixture" of both approaches serves this delicate issue on the didactics of introductory QM best.
After the dust of the initial disturbance of the students' (and usually also the teachers') minds by quantum theory has settled, the state description boils down to the following.
A quantum state is uniquely defined by a self-adjoint positive semidefinite operator \hat{\rho} (the Statistical Operator) with trace 1 on an appropriate Hilbert space \mathcal{H}.
Special Statistical operators are projection operators, \hat{\rho}_{\psi}=|\psi \rangle \langle \psi |, called "pure states" as opposed to "mixed states" that are no projection operators. Here |\psi \rangle is some Hilbert-space vector with norm 1.
Defining states in this way, no trouble like the here discussed thing occur with half-integer spins. The reason is that obviously not the normalized Hilbert-space vector |\psi \rangle characterizes a certain pure state but a whole equivalence class of such vectors, because obviously with |\psi' \rangle=\exp(\mathrm{i} \varphi) |\psi \rangle with \varphi \in \mathbb{R} we have
\rho_{\psi'}=|\psi ' \rangle \langle \psi'|=|\psi \rangle \langle{\psi}|=\rho_{\psi},
and thus |\psi' \rangle represents the same state as |\psi \rangle. Thus a phase factor doesn't matter to the state representation, i.e., a state is not characterized by the state ket itself but by the whole equivalence class of state vectors, which just deviate from each other by some phase factor. This is called a (unit) ray in Hilbert space.
This is a quite important issue, if it comes to the very foundations of the notion of a half-integer spin from the first place. A much better "correspondence principle" than the pretty handwaving "canonical quantization procedure" (in brief substituting Poisson brackets in classical mechanics by commutators of self-adjoint operators (times a purely imaginary factor), representing observables in the Hilbert space of quantum mechanics): You use the symmetry properties of the system. The most general symmetry is that of the underlying space-time model (e.g., as discussed here the Galileo symmetry of Newtonian space-time) to define the observable algebra of quantum mechanics (e.g., generators of spatial translations are called components of momentum, of temporal translations (time evolution) energy or Hamiltonian, and so on).
If it comes to the analysis of the rotation group and thus, attacking the somewhat simpler representation theory of the corresponding Lie algebra first, one automatically finds not only the integer-spin representations but also the half-integer-spin representations (if you don't stick to orbital angular momentum but first consider the abstract Lie algebra of the rotation group, which is just the angular-momentum algebra of quantum theory because angular momentum is the generator of rotations).
If you would now assume that the Hilbert-space vectors themselves (and not more correctly the rays in Hilbert space), you'd conclude that you must exclude half-integer-spin right away, because otherwise you'd really have the paradox stated in the original posting. But this contradicts the observation that there are particles with half-integer spin like the most common around us, nucleons and electrons! This shows that indeed we must represent pure states by the rays (or equivalently by the pure-state Statistical Operators) rather than the Hilbert-space vectors themselves als discussed above.
There is another interesting twist to these considerations, namely the appearance of super-selection rules! The phase factors of state kets become observable as soon as one considers superpositions of vectors and the various vectors in the superposition change their relative phase (rather than an overall phase for all of them, which doesn't change the state as discussed above), because the relative phase is in principle observable when measuring observables that are sensitive to interference effetcts of the superposition.
This, however implies, that there must never by superpositions of states with half-integer spin and integer spin, because then you really have a paradox, even in the refined definition of states discussed above! Suppose we have a vector |\psi_i \rangle with integer and one with half-integer spin |\psi_h \rangle. Now consider the superposition
|\psi \rangle=|\psi_i \rangle + |\psi_{h} \rangle
and assume that we have properly normalized this vector to have norm 1 as to serve as an representant of a ray to describe a state.
Now for spin to make sense at all the whole formalism must admit rotations as a unitary transformations (this is also a pretty interesting statement, related to the Bargmann-Wigner theorem, which is worth to be studied in this context too). Now you can consider a rotation with rotation angle 2 \pi around an arbitrary axis. Then the above superposition becomes
\hat{R}(2 \pi) |\psi \rangle = |\psi_i \rangle - |\psi_{h} \rangle.
But this is not just the original state multiplied by an overall phase factor, but the relative phase between the two vectors in the superposition changes, i.e., through a rotation around 2 \pi you get really another ray, and thus another state of the system. On the other hand, such a rotation must be as good as doing nothing to the system, and this means that such superpositions must be forbidden to keep the whole edifice of the theory consistent! This is an example for a superselection rule, and indeed, until today one has never observed any states that are such "forbidden superpositions" of an integer- and a half-integer-spin state.
