Sequences with 3 letters
Here is a sketch of a proof that there are no such complete sequences for $n>4$.
Consider the graph where the vertices are the triples of nonnegative integers that sum to $n$ and construct an edge between two vertices when one can get from one to the other by incrementing one element and decrementing another. This graph looks like a triangle tiled by smaller triangles, in particular it is planar, so two paths cannot cross without intersecting. A solution of the original problem induces a hamiltonian path on this graph.
Now look at the extreme vertices of the triangle $(0,0,n)$, $(0,n,0)$, and $(n,0,0)$. In the original problem, a path of length n that starts or ends at one of these points must end or start at the opposite edge. As the induced path cannot cross itself, if the three vertices are all on a path, they must occur adjacent to each other, so the path looks like wlog $*0^n1^n2^n*$. This means that two sides of the triangle are occupied so neither the prefix nor the suffix can be longer than $(n-1)$, and if $n>4$ there are more than $2n-2$ elements that don't lie on the two edges.
ADDED: I have translated this problem into a somewhat annoying javascript toy. This makes it somewhat easier to see the structure in Robert Israel's solutions. I am fairly convinced (but still cannot prove) that the size of the optimal solution grows quadratically, and I would not be surprised if the optimal solution covered all but a linear in $n$ number of combinations.