In the comments to the question, Jyrki showed that if $n$ has a square factor then there are nontrivial ${\mathbf Q}$-linear relations among $\{\zeta_n^a : (a,n) = 1\}$, so this set can only be a ${\mathbf Q}$-basis of ${\mathbf Q}(\zeta_n)$ when $n$ is squarefree. To show that when $n$ is squarefree the set $\{\zeta_n^a : (a,n)=1\}$ is a ${\mathbf Q}$-basis of ${\mathbf Q}(\zeta_n)$ we will use induction on the number of prime factors of $n$.
Suppose first that $n = p$ is a prime. The usual ${\mathbf Q}$-basis of ${\mathbf Q}(\zeta_p)$ is $\{1,\zeta_p,\zeta_p^2,\cdots,\zeta_{p}^{p-2}\}$. Since $\zeta_p^{p-1} = -1-\zeta_p - \cdots - \zeta_p^{p-2}$, if we replace $1$ with $\zeta_p^{p-1}$ we still have a ${\mathbf Q}$-basis, so $\{\zeta_p,\zeta_p^2,\cdots,\zeta_p^{p-1}\}$ is a basis of ${\mathbf Q}(\zeta_p)/{\mathbf Q}$.
Now suppose we've proved the result when $n$ is any product of $r$ primes and consider a squarefree positive integer $n$ that is a product of $r+1$ primes. Write $n = mp$ where $p$ is one of the prime factors of $n$, so we know $\{\zeta_m^i : 1 \leq i \leq m, (i,m) = 1\}$ is a ${\mathbf Q}$-basis of ${\mathbf Q}(\zeta_m)$ and $\{\zeta_p^{j} : 1 \leq j \leq p, (j,p) = 1\}$ is a ${\mathbf Q}$-basis of ${\mathbf Q}(\zeta_p)$. From Galois theory, if $E$ and $F$ are (finite) Galois extensions of a common field $L$ and $E \cap F = L$ then as a basis of $EF$ over $L$ one can use the set of products $\{e_if_j\}$ where $\{e_i\}$ is any $L$-basis of $E$ and $\{f_j\}$ is any $L$-basis of $F$. We can apply this to the fields $E = {\mathbf Q}(\zeta_m)$, $F = {\mathbf Q}(\zeta_p)$, and $L = {\mathbf Q}$. (That the intersection of those two cyclotomic fields is ${\mathbf Q}$ is a special case of a general formula ${\mathbf Q}(\zeta_r) \cap {\mathbf Q}(\zeta_s) = {\mathbf Q}(\zeta_{(r,s)})$, which becomes ${\mathbf Q}$ when $r$ and $s$ are relatively prime.) Therefore a ${\mathbf Q}$-basis of $EF = {\mathbf Q}(\zeta_m,\zeta_p) = {\mathbf Q}(\zeta_n)$ is the set of products $\{\zeta_m^i\zeta_p^j\}$ with $i$ and $j$ running over the integers listed earlier. Inside ${\mathbf Q}(\zeta_n)$ we can use $\zeta_m := \zeta_n^{n/m}$ and $\zeta_p := \zeta_n^{n/p}$, so a basis is $\{\zeta_n^{(n/m)i + (n/p)j}\} = \{\zeta_n^{pi + mj}\}$ where $i$ runs over integers from 1 to $m$ which are relatively prime to $m$ and $j$ runs over integers from 1 to $p$ which are relatively prime to $p$ (that is, $1 \leq j \leq p-1$).
Which $n$th roots of unity are in the set $\{\zeta_n^{pi + mj}\}$ and how many are there? The integers $pi+mj$ are all relatively prime to $n = mp$ (just reduce them mod $m$ and mod $p$ to check they are relatively prime to $m$ and $p$ separately), so the set consists of primitive $n$th roots of unity. If pi + mj \equiv pi' + mj' \bmod n (where i' and j' are just second choices of parameters) then by reducing mod $m$ and mod $p$ we get i \equiv i' \bmod m and j \equiv j' \bmod p, so i = i' and j = j' on account of the ranges of these parameters. Therefore the number of roots of unity in this set is $\varphi(m)\varphi(p) = \varphi(n)$, so our set is exactly the set of all primitive $n$th roots of unity. This completes the proof that the primitive $n$th roots of unity are a ${\mathbf Q}$-basis of ${\mathbf Q}(\zeta_n)$ when $n$ is squarefree.
Although the question has now been answered, let me indicate a place where it naturally fits into a broader picture within algebraic number theory. The result is related to a theorem of Emmy Noether on normal integral bases.
For any (finite) Galois extension $K/{\mathbf Q}$, a normal integral basis is a normal basis for the field extension which consists of a ${\mathbf Z}$-basis of ${\mathcal O}_K$. For example, ${\mathbf Q}(\sqrt{5})/{\mathbf Q}$ has normal integral basis $\{(1+\sqrt{5})/2,(1-\sqrt{5})/2\}$. Another example is ${\mathbf Q}(\zeta_p)$ for any odd prime $p$: the ring of integers is ${\mathbf Z}[\zeta_p]$ and the usual ${\mathbf Z}$-basis you may want to use is $\{1,\zeta_p,\cdots,\zeta_p^{p-2}\}$, but that's not a normal basis because it has 1 in it. Instead you can use $\{\zeta_p,\zeta_p^2,\cdots,\zeta_p^{p-1}\}$; that is a normal basis and it's also a ${\mathbf Z}$-basis of ${\mathbf Z}[\zeta_p]$, so ${\mathbf Q}(\zeta_p)/{\mathbf Q}$ has a normal integral basis.
Here's an example without a normal integral basis. If $d$ is squarefree and not $1 \bmod 4$, the ring of integers of ${\mathbf Q}(\sqrt{d})$ is ${\mathbf Z}[\sqrt{d}]$. A normal basis over ${\mathbf Q}$ has the form $\{a+b\sqrt{d},a-b\sqrt{d}\}$ for rational $a$ and $b$ with $b \not= 0$. If this basis is in ${\mathbf Z}[\sqrt{d}]$ then it can't be a ${\mathbf Z}$-basis of ${\mathbf Z}[\sqrt{d}]$ because ${\mathbf Z}(a+b\sqrt{d}) + {\mathbf Z}(a-b\sqrt{d})$ has index $2|ab| \geq 2$ inside ${\mathbf Z}[\sqrt{d}]$.
The ring of integers of ${\mathbf Q}(\zeta_n)$ is ${\mathbf Z}[\zeta_n]$. Check that if $\{\zeta_n^a : (a,n) = 1\}$ were a basis of ${\mathbf Q}(\zeta_n)/{\mathbf Q}$ then it would be a ${\mathbf Z}$-basis of ${\mathbf Z}[\zeta_n]$, hence the $n$-th cyclotomic field would have a normal integral basis.
Emmy Noether proved that if a Galois extension $K/{\mathbf Q}$ has a normal integral basis then $K$ is tamely ramified over ${\mathbf Q}$. So being tamely ramified is a necessary (although generally not sufficient) condition for a Galois extension of ${\mathbf Q}$ to have a normal integral basis. For example, if $d$ is squarefree and $d \not\equiv 1 \bmod 4$ then 2 is not tamely ramified in ${\mathbf Q}(\sqrt{d})$, so Noether's theorem implies that this quadratic field has no normal integral basis over ${\mathbf Q}$, which we already proved by a direct computation above. An example more relevant for us here is ${\mathbf Q}(\zeta_{p^2})$. The prime $p$ is not tamely ramified in this field, so any cyclotomic field ${\mathbf Q}(\zeta_n)$ with $n$ divisible by the square of a prime is not tamely ramified at that prime, hence it doesn't have a normal integral basis. Therefore a necessary condition for $\{\zeta_n^a : (a,n) = 1\}$ to be a normal basis of the $n$-th cyclotomic field is that $n$ is squarefree. Noether's theorem has provided a conceptual explanation for why $n$ must be squarefree.
I suggest looking at Robert Long's book "Algebraic Number Theory" for more information on tamely ramified extensions of ${\mathbf Q}$ and the relation to normal integral bases. I don't have the book in front of me right now and Google Books is not giving good views of it, but I'm pretty sure he has a chapter on this topic in it since Galois module structure was one of his areas of interest.