This problem is part of exercise 2.17 in Nielsen and Chuang's textbook, and has been already answered on this site in this post.
I understand that because $A$ is normal, it can be orthogonally diagonalized
\begin{equation} A = U^*DU \end{equation}
where $U$ is orthonormal.
What I do not understand is the claim that $U^*U = UU^* = I$, where $^*$ denotes conjugate-transpose. I know that orthonormal matrices satisfy $UU^T = I$, where $^T$ is transpose. But if $U$ has complex entries, then conjugate-transpose should not in general equal transpose alone.
You are mistaken when you write that “because $A$ is normal, it can be orthogonally diagonalized $A=U^∗DU$, where $U$ is orthonormal.” Being normal is equivalent to the assertion that $A$ is unitarily diagonalizable.