I suggested in a comment, to look for colorings that are the same for each a, except for a fixed permutation.
Suppose the colors are given by function c(x), for x ≥ 1. And a permutation function p(i,j), where i,j ∈ [1..n]. Where i is the index of the permutation, and j the index of the permutation of the color.
If n = 4 and the coloring starts with abcd, then p(1,1) = a, p(1,2) = b, p(1,3) = c, p(1,4) = d, p(2,1) = b, p(2,2) = d.
If the coloring is the same for each a, then we get the following equation:
c(an) = p(c(a),c(n))
From this it follows, that the permutation must p(i,j)=p(j,i).
However, it is more important to give a condition when a coloring can be constructed:
Lemma 1: If p(x,y) = p(v,w) for xy = vw, then a coloring can be constructed.
Lemma 2: For each n a permutation exists such that p(x,y) = p(v,w) for xy = vw.
To see how this works, for n = 4, we start the following permutation matrix:
abcd
bd..
c...
d...
Fill in the second row:
abcd
bdac
ca..
dc..
And complete it:
abcd
bdac
cadb
dcba
From this construct the coloring: abcdxaxcdxxbxxxa
By each prime number > n (the x values in the coloring), you can choose a color, but you have to continue with the permutation of that color.
Lemma 1 is trivial to prove, because it follows that c(xy) is c(yx).
I haven't proven lemma 2 yet. For n is 1,2,3,4, there is only 1 permutation matrix. For n = 5 there are a few. The condition p(x,y) = p(v,w) for xy = vw becomes relative weaker for larger n. So, I don't think it is a problem to create such permutation matrix (also given the number of different Sudokus). Of course, lemma 2 needs to be proven properly.
Edit: For Lema 1, it might be necessary to add an associativity condition. That p(x,p(y,z)) = p(p(x,y),z). With associativity, the proof is trivial. I don't know if it can be done without.
Edit 2: The associativity condition is indeed necessary. And this is also part of the solution. If you have a permutation that consists of 1 cycle, then the full permutation matrix can be created by applying the permutation multiple times. This ensures the associativity condition.
It is important that after n times applying the permutation, the colors are in original order again. This means that for n = 5, you must have 1 cycle, because one cycle of 3 plus one cycle of 2 does not come in original order after applying 5 times.
However, this does not count for n = 6. The solution of François as matrix looks like this:
abcdef
bdface
cfbead
daebfc
ecafdb
fedcba
The first permutation, brings you from ato b, from b to d and back to a. However, this can still be categorized as 1 cycle permutation, if you look the permutation from 1 row to third row. a->c->b->f->d->e->a.
I think it is not difficult to create a coloring with a permutation of 1 cycle. You only need to ensure that the few multiplications that are below n fit, and then create the permutation to have 1 cycle. I think for larger n, there is plenty of possibilities for that.