OK, I now have a counter-example. Thanks to the previous answers for showing me where to look.

Let $A = k[x,y,z]$. Let $M$ be the kernel of the map $(x,y,z) : A^3 \to A$ and $N$ the co-kernel of the map $(x,y,z)^T: A \to A^3$. I claim that $M = N^{*}$ but $M$ is not free.

To see that $M=N^{*}$, consider the defining sequence
$$0 \to A \to A^3 \to N \to 0.$$
This gives rise to
$$0 \to N^{*} \to A^3 \to A.$$
The kernel of the right hand map is $M$ by definition.

Now, let's see that $M$ is not free. We have a graded short exact sequence
$$0 \to M \to A^3 \to A[1] \to k[1] \to 0.$$
So the Hilbert series of $M$ is 
$$\frac{3}{(1-t)^3} - \frac{t^{-1}}{(1-t)^3} + t^{-1} = \frac{(1-t)^3 - 1 + 3t}{t(1-t)^3} = \frac{3t-t^2}{(1-t)^3}.$$
If $M$ were a free module, its Hilbert series would look like $(t^a+t^b)/(1-t)^3$.

$N$ is also not free; I have not figured out whether $N$ is reflexive.