Solution:

We will assume that there is a coloring with $n+1$ colors and derive a contradiction. For each string $s$, let $T_{s}$ be the set consisting of all strings that differ from $s$ in at most 1 place. Thus $T_{s}$ has size $n+1$ and all vertices in $T_{s}$ are adjacent. In particular, if there is an $(n+1)$-coloring, then each color is used exactly once in $T_{s}$.

Let $c$ be one of the colors that we used. We will determine how many vertices are colored with $c$. We will do this by counting in two ways.

Let $k$ be the number of vertices colored with color $c$. Each such vertex is part of $T_{s}$ for exactly $n+1$ values of $s$. On the other hand, each $T_{s}$ contains exactly one vertex with color $c$. It follows that $k(n+1) = 2^{n}$.

In particular, since $k$ is an integer, $n+1$ divides $2^{n}$. This is a contradiction since $n+1$ is not a power of $2$ by assumption, so actually there can be no $n+1$-coloring, as claimed.