I think the inconsistency appears because the transpose $X^{\rm t}$ is missing in your answer. Let me try to work this out, along the lines of this <A HREF="http://mathoverflow.net/questions/194840/some-calculus-in-the-orthogonal-group-on/194900#194900">similar calculation</A> in the orthogonal (rather than unitary) group.

We need the fourth-order tensor
$$\int_{{\rm U}(n)}(U^m)_{ij}(U^m)^*_{kl}\,dU=a_{m}(n)\delta_{ij}\delta_{kl}+b_{m}(n)\delta_{ik}\delta_{jl}+c_{m}(n)\delta_{il}\delta_{jk}$$
so that the required integral takes the form
$$\int_{{\rm U}(n)}U^m X(U^\dagger)^m\,dU=a_{m}(n)X+b_{m}(n)\mathbb{1}\,{\rm tr}\,X+c_{m}(n)X^{\rm t}
$$
by taking traces I find, using theorem 2 from <A HREF="http://statweb.stanford.edu/~cgates/PERSI/papers/random_matrices.pdf">Diaconis and Shahshahani</A>, that
<!--
$$na_{pq}(n)+nb_{pq}(n)+n^2 c_{pq}(n)=\int_{{\rm O}(n)}{\rm tr}\,g^{p+q}\,dg=\begin{cases}
0&{\rm if}\;\;p+q\;\;\text{is an odd integer}\\
1&{\rm if}\;\;p+q\;\;\text{is an even integer}
\end{cases}
$$
$$n^2a_{pq}(n)+nb_{pq}(n)+nc_{pq}(n)=\int_{{\rm O}(n)}({\rm tr}\,g^p)({\rm tr}\,g^q)\,dg=\begin{cases}
p&{\rm if}\;\;p=q\;\;{\rm odd}\\
p+1&{\rm if}\;\;p=q\;\;{\rm even}\\
1&{\rm if}\;\;p\neq q\;\;\text{both even}\\
0&{\rm otherwise}
\end{cases}
$$
$$na_{pq}(n)+n^2 b_{pq}(n)+nc_{pq}(n)=\int_{{\rm O}(n)}{\rm tr}\,g^{|p-q|}\,dg=\begin{cases}
0&{\rm if}\;\;p+q\;\;\text{is an odd integer}\\
1&{\rm if}\;\;p+q\;\;\text{is an even integer}
\end{cases}
$$
Three equations with three unknowns give
$$
a_{pq}=\frac{-2}{(n-1)(n+2)},\;\;b_{pq}=c_{pq}=\frac{n}{(n-1)(n+2)}\;\;\mbox{if $p\neq q$ both odd}$$
$$
a_{pq}=b_{pq}=c_{pq}=\frac{1}{n+2},\;\;\mbox{if $p\neq q$ both even}$$
$$a_{pq}=1-(n+1)b_{pq},\;\;b_{pq}=c_{pq}=\frac{n-p}{(n-1)(n+2)}\;\;\mbox{if $p=q$ odd}$$
$$a_{pq}=1-(n+1)b_{pq},\;\;b_{pq}=c_{pq}=\frac{n-p-1}{(n-1)(n+2)}\;\;\mbox{if $p=q$ even}$$
-->