We simply translate the binary result of a qubit measurement to our guess whether it's the first state or the second, calculate the probability of success for every possible measurement of the qubit, and then more find the maximum of a function of two variables (on the two-sphere).
First, something that we won't really need, the precise description of the state. The full state of the system that depends both on superpositions a well as a classical fair coin may be encoded in the density matrix
$$ \rho = \frac 12 \pmatrix{1&0\\0&0} + \frac 12 \pmatrix{\cos^2x &\sin x \cos x\\ \sin x\cos x & \sin^2 x} $$
where the left column and upper row corresponds to the basis state "zero" and the remaining ones to "one". It's helpful to rewrite the density matrix in terms of the 4-element basis of the $2\times 2$ matrices,
$$ \rho = \frac 12+ \frac{\sin x \cos x}{2} \sigma_x + \left(\frac{\cos^2 x - \sin^2 x}{4}+\frac 14\right) \sigma_z $$
That may be written in terms of the angle $2x$:
$$\rho = \frac 12 + \frac {\sin 2x}{4} \sigma_x + \frac{\cos 2x +1}{4} \sigma_z $$
Now, regardless of the mixed state, this is still a two-level system and all measurements on the two-dimensional Hilbert space are either trivial (measurements of a $c$-number) or equivalent to the measurement of the spin along an axis, i.e. measurements of
$$ V = \vec n \cdot \vec \sigma $$
which is a unit 3D vector multiplied by the vector of Pauli matrices. OK, what happens if we measure $V$? The eigenvalues of $V$ are plus one or minus one. The probability of each may be obtained from the expectation value of $V$ which is
$$\langle V \rangle = {\rm Tr} (V \rho) $$
The traces of products only contribute if $1$ meets $1$ (but we assume there was no term in $V$) or $\sigma_x$ meets $\sigma_x$ etc., in which cases the trace of the matrix gives an extra factor of 2. So we have
$$\langle V \rangle = \frac{\sin 2x}{2}n_x + \frac{\cos 2x +1}{2} n_z $$
We get the eigenvalue $\pm 1$ with the probabilities $(1\pm\langle V \rangle) / 2$, respectively. Exactly when $\cos x = 0$, the two initial "head and tail" states are orthogonal to one another (basically $|0\rangle$ and $|1\rangle$) and we may fully discriminate them. To make the probabilities $0,1$, we must simply choose $\vec n=(0,0,\pm 1)$; note that the overall sign of $\vec n$ doesn't matter for the procedure.
Now, for $\cos x \neq 0$, the states are non-orthogonal i.e. "not mutually exclusive" in the quantum sense and we can't measure directly whether the coin was tails or heads because those possibilities were mixed in the density matrix. In fact, the density matrix contains all probabilities of all measurements, so if we could get the same density matrix by a different mixture of possible states from coin tosses, the states of the qubit would be strictly indistinguishable.
Our probability of success will be below 100% if $\cos x\neq 0$. But the only meaningful way to use the classical bit $V=\pm 1$ from the measurement is to directly translate it to our guess about the initial state. Without a loss of generality, our translation may be chosen to be
$$ (V = +1) \to |i\rangle = |0\rangle \\ $$
and
$$ (V = -1) \to |i\rangle = \cos x |0\rangle + \sin x |1 \rangle.$$
If we wanted the opposite, cross-identification of the heads-tails and the signs of $V$, we could simply achieve it by flipping the overall sign of $\vec n \to -\vec n$.
Let's call the first simple initial state "heads" (the zero) and the second harder one "tails" (the cosine-sine superposition). The probability of success is, given our translation from $+1$ to heads and $-1$ to tails,
$$ P_{\rm success} = P(H) P(+1|H) + P(T) P(-1|T). $$
Because it's a fair coin, the two factors included above are $P(H)=P(T)=1/2$. The most difficult calculation among the four probabilities is $P(-1|T)$. But we have already made a harder calculation above, it was the $(1-\langle V\rangle) / 2$. Here we just omit the constant term proportional to $n_z$ and multiply by two:
$$ P(-1|T ) = \frac 12 - \sin 2x \frac{ n_x}2 - \cos 2x \frac{ n_z}2 $$
The result for "heads" is simply obtained by setting $x=0$ because the "heads" state equals "tails" states with $x=0$ substituted. So
$$ P(-1|H) = \frac{1-n_z}{2} $$
and the complementary $1-P$ probability is
$$ P(+1|H) = \frac{1+n_z}{2} $$
Substitute those results to our "success probability" to get
$$P_{\rm success} = \frac{1+n_z +1 - (\sin 2x)n_x - (\cos 2x)n_z}{4} $$
or
$$P_{\rm success} = \frac 12 - \frac{n_x}4 \sin 2x + \frac{n_z}{4} (1-\cos 2x ) $$
If we define $(n_x,n_z)=(-\cos \alpha,-\sin\alpha)$, we may also write it as
$$ P_{\rm success} = \frac 12 +\frac{\sin(2x+\alpha)-\sin \alpha}{4} =\frac 12+\frac{\sin x \cos(x+\alpha)}{2} $$
We want to maximize that over $\alpha$. Clearly, the maximum is for $\cos(x+\alpha)=\pm 1$ where the sign agrees with that of $\sin x$ i.e. $\alpha=-x$ or $\alpha=\pi -x $ and the value at this maximum is
$$ P_{\rm success} = \frac{1+|\sin x|}{2}$$
which sits in the interval 50% and 100%.
That's a nice measurement which is really quantum mechanical. We use a different measurement than that of $\sigma_z$, i.e. the classical measurement of the bit. Instead, we measure the spin along the axis in the $xz$-plane that is defined by the same nonzero angle as the angle $x$ at the beginning, with some correct signs and shifts by multiples of $\pi/2$. Note that if you measured simply $\sigma_z$, the classical bit, the success rate would be just $(3-\cos 2x)/4$, also between 50% and 100%, but smaller than our result. In particular, for a small $x=0+\epsilon$, our optimal result would be Taylor-expanded as $1/2+|x|/2$ while the non-optimum result using the classical measurement would increase above $1/2$ more slowly, as $1/2+x^2/2$.
For many hours, a wrong answer (a mistake in the final portions) was posted here, despite the fact that I had previously fixed many wrong factors of two. I posted a slightly edited version of this answer on my weblog where some discussion may take place:
The Reference Frame: A fun simple problem in quantum computing
On that page, I also write the eigenstates of the measured operator in the appendix. The arguments in the angles may be surprising for some folks who think that this problem is obvious in terms of the wave functions or that the wave functions after the measurement have to be simple.
