I was wondering if the fenchel conjugate of the $\frac{1}{2}||u||^2$, is the $\frac{1}{2}||u||_*^2$, where $||.||_*$ is the dual norm of $||.||$. This seems to be true for the $\ell_2$ norm. However, I do not seem to be able to prove it in general.
Does anyone know if this is even true in general?
Yes, this is true. Please see page 93-94 in the book "convex optimization" https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf