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 a <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}(\bar{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}
$$
substitution $X=\mathbb{1}$ gives a first relation
$$a_m(n)+nb_m(n)+c_m(n)=1$$
one more relation follows from application of theorem 2.1.b of <A HREF="http://statweb.stanford.edu/~cgates/PERSI/papers/functionals.pdf">Diaconis and Evans</A>:
$$n^2 a_m(n)+nb_m(n)+nc_m(n)=\int_{{\rm U}(n)}\,({\rm tr}\,U^m)({\rm tr}\,\bar{U}^m)\,dU={\rm min}\,(n,m)$$
I need a third relation
$$na_m(n)+nb_m(n)+n^2 c_m(n)=\int_{{\rm U}(n)}\,{\rm tr}\,(U^m\bar{U}^{m})\,dU\equiv y_m(n)$$
This third integral remains to be evaluated, I will do that later today.