As far as I can see, this question has a simple solution.

Let's limit ourselves to Hamiltonian cycles, and forget about the constraint that the coloring is legal.

**Theorem:**
Let $c$ be an edge-coloring of $K_n$ such that no two Hamiltonian cycles have the same set of colors. Then $c\geq (1+o(1))\left(\frac{n}{e}\right)^2$.

**Proof:** There are $(n-1)!/2$ Hamiltonian cycles, and $\sum_{i=1}^{n} \binom{c}{i}$ subsets of $c$ of size at most $n$. As each Hamiltonian cycle corresponds to a different such subset, we get the inequality
$$
(n-1)!/2 \leq \sum_{i=1}^{n} \binom{c}{i}.
$$
Recalling that $(n-1)!/2=((1+o(1))\left(\frac{n}{e}\right))^n$ and that (for $c>2n$, which we can assume here) $\sum_{i=1}^{n} \binom{c}{i}=((1+o(1))\left(\frac{c \cdot e}{n}\right))^n$, we have
$$
((1+o(1))\left(\frac{n}{e}\right))^n\leq\left(\frac{c \cdot e}{n}\right)^n ,
$$
which yields the theorem.