You were going along fine until you got to this point:
\begin{align}
P\left\{\textrm{Yes}\right\} &= p/2 + 1/4
\end{align}
That gives you the probability of a "yes" for any particular subject. Now, suppose you have an experiment with $N$ subjects of whom $n$ answered "yes." What is the maximum likelihood estimator of $p$? Well, the likelihood and log likelihood functions are (ignoring unimportant combinatoric terms):
\begin{align}
L &= \left(p/2+1/4\right)^n\left(1-p/2-1/4\right)^{N-n}\\
lnL &= n \cdot \ln{\left(p/2+1/4\right)} + (N-n) \cdot \ln{\left(1-p/2-1/4\right)}
\end{align}
Maximize with respect to $p$:
\begin{align}
\frac{dlnL}{dp} = n \cdot \frac{1}{p/2+1/4} \frac{1}{2} + (N-n) \cdot \frac{1}{1-p/2-1/4}\frac{-1}{2}=0
\end{align}
Solving . . .
\begin{align}
\frac{n}{p/2+1/4}&=\frac{N-n}{1-p/2-1/4}
\end{align}
After several algebra steps . . .
\begin{align}
\hat{p} &= 2\frac{n}{N}-\frac{1}{2}
\end{align}
This is pretty much what you got. Just as you say, the problem is that for high values of $n$, which (contrary to another answer) definitely can happen in small samples, this gives an estimator for which $\hat{p}>1$. For small enough values of $n$, you can get a $\hat{p}<0$.
So, what gives? What gives is that we have neglected to state the constraints on the maximization problem. The probability of a "yes" must lie between 0 and 1: that is $0 \le p \le 1$. This is a constraint on the maximization which we may NOT ignore (well, in large samples we can, but never mind that). In more typical derivations of maximum likelihood estimators, we just ignore the constraints and everything works out OK. This is fine if everything works out OK (that is if we find an interior maximum and the log likelihood is concave). If everything does not work out OK, then we have to pay attention to the constraints.
To be really careful, we could go back and write the maximization down as a constrained maximization. This would introduce two lagrange multipliers, one for the $p\ge0$ constraint and one for the $p\le1$ constraint. There is no need to do this, however. Since the log likelihood is concave, we can just impose the constraints ex post.
So, here is the maximum likelihood estimate:
\begin{equation}
\hat{p} = \left\{ \begin{array}{l}
0 \; \textrm{if} \quad 2\frac{n}{N}-\frac{1}{2} < 0\\
1 \; \textrm{if} \quad 2\frac{n}{N}-\frac{1}{2} > 1\\
2\frac{n}{N}-\frac{1}{2} \qquad \textrm{otherwise}
\end{array}
\right.
\end{equation}
Obviously, the normal way of making confidence intervals won't work for cases where you are pinned against the costraints. The simplest thing to do is to bootstrap the confidence intervals.
Finally, you can use your data to test whether the subjects are following your instructions. If they are following your instructions, then $P\{\textrm{Yes}\} \ge 1/4$ and $P\{\textrm{Yes}\} \le 3/4$. These hypotheses can be tested with a likelihood ratio test using your data.
If you have the problem you are worrying about, you should suspect that the subjects are disobeying you on the coin-tossing business. In a large sample, if the subjects are obeying you, then you can't have the problem you are worrying about, except with very small probability.
