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.