Thinking about this problem again, I found the following simpler explanation which does not invoke orthogonal polynomials and uses the nonvanishing of only one Hankel determinant. The determinant arises via Padé approximants but the exposition below is self-contained.

Suppose in general that $a_0 \neq 0$, $a_1, a_2, \ldots, a_{q-1}$ are elements of a finite field $F$ of $q$ elements for which the polynomial
$$
A(X) = \sum_{i=0}^{q-1} \phantom. a_i X^i
$$
vanishes at all but $t$ nonzero field elements, say $x_1,x_2,\ldots,x_t$, with $2t < q-1$. Then
$$
A(x) = \frac{P(x)}{Q(x)} (1 - x^{q-1})
$$
for some polynomials $P,Q$ of degree $t$, where
$$
Q(X) = \prod_{m=1}^t (X-x_m) = \sum_{i=0}^t \phantom. q_i X^i
$$
for some field elements $q_i$. Thus $A(X)$ is within $O(X^{q-1})$ of the power series about $X=0$ of the degree-$t$ rational function $P(X)/Q(X)$. For any $t' \in [t, \phantom. (q-1)/2)$ and $n \in (0, \phantom. q-1-2t')$ it follows that the square Hankel matrix
$$
(a_{n+i+j})_{i,j=0}^{t'} = \left(
\begin{array}{ccccc}
a_n & a_{n+1} & a_{n+2} & \cdots & a_{n+t'} \\
a_{n+1} & a_{n+2} & a_{n+3} & \cdots & a_{n+1+t'} \\
\vdots & \vdots & \vdots & & \vdots \\
a_{n+t'} & a_{n+t'+1} & a_{n+t'+2} & \cdots & a_{n+2t'}
\end{array}
\right)
$$
of order $t'+1$ is singular, because the nonzero column vector
$(0,0,\ldots,0,q_d,q_{d-1},q_{d-2},\ldots,q_1,q_0)^{\rm T}$ [with $t'-t$ initial zeros] is in the kernel. Thus a single invertible matrix of this form implies that there are more than $t' \geq t$ nonzero $x\in F$ at which $A(x) \neq 0$.

To apply this to the Putnam problem, take $q=p$ and $a_i = i!$, and set $t' = t = \frac12(p-1) - 1$ and $n=1$. The resulting Hankel matrix $((i+j+1)!)_{i,j=0}^t$ is invertible mod $p$ thanks to the formula $\prod_{k=0}^t k!(k+1)!$ for its determinant. [This formula can be obtained from properties of the Laguerre orthogonal polynomials, but also has an elementary direct proof: see the second solution of this problem at the Putnam directory.] Hence $A(x) \neq 0$ for at least $t+1 = (p-1)/2$ nonzero values of $x \bmod p$, **QED**.

It is also known that the Hankel matrix $(a_{i+j})_{i,j=0}^t$ *is* invertible, else we'd have $P/Q \equiv P_1/Q_1 \bmod X^{2t}$ for some $P_1,Q_1$ of degree less than $t$, whence $P/Q = P_1/Q_1$ identically and $P/Q$ is not in lowest terms. This lets us connect the above solution with the orthogonal polynomials evaluated at $X^{-1}$ that arose in our previous solution. Indeed, define a bilinear pairing $\langle\cdot,\cdot\rangle$ on $F[X]$ by $\langle P,Q \rangle = I(PQ)$, where $I: F[X] \rightarrow F$ is the linear form taking each $X^i$ to $a_i$. The restriction of this pairing to the polynomials of degree at most $t$ is nondegenerate because its Gram matrix is the Hankel matrix we just proved invertible. But $G(X) := X^t Q(1/X) = \sum_{i=0}^t q_i X^{d-i}$ is orthogonal to $X^j$ for each $j = 1,2,\ldots,t+1$. Hence $XG$ is orthogonal to every polynomial of degree at most $t$, and is therefore a multiple of the orthogonal polynomial of degree $t+1$ for our inner product (which is unique up to scaling thanks to the nondegeneracy of the pairing). It follows that in this case the orthogonal polynomial of degree $t+1$ must vanish at zero and at $t$ other elements of $F$. This does not happen often for classical orthogonal polynomials, but (as noted in my previous answer) there is at least one infinite family of examples, the Čebyšev polynomials of the second kind $U_{(q-1)/2}$ when $q \equiv 3 \bmod 4$.