For Hermitian matrices $A$ and $B$, diagonalizing each unitary matrix $e^{iA}$ and $e^{iB}$ gives
\begin{equation} \text{Tr}(e^{iA}e^{iB}) = \text{Tr}(U^* e^{iD_A}UV^*e^{iD_B}V), \end{equation} where $D_A$ and $D_B$ are diagonal matrices of $A$ and $B$ respectively. Then, by using cyclic property of trace and defining a new unitary operator $X = UV^*$, the above equation equals to
\begin{equation} = \text{Tr}(X^* e^{iD_A}X e^{iD_B}). \end{equation} Choosing a complete orthonormal basis set $\{\lvert i \rangle\}$ (using braket-notation) and another complete orthonormal basis set $\{\lvert j \rangle\}$ that includes $\lvert i \rangle$, we further have \begin{equation} = \sum_i \langle i \rvert X^* e^{iD_A}X e^{iD_B}\lvert i \rangle = \sum_i\langle i \rvert X^* e^{iD_A}X \big(\sum_j \lvert j \rangle \langle j\big) \rvert e^{iD_B}\lvert i \rangle = \sum_i\langle i \rvert X^* e^{iD_A}X \lvert i\rangle\cdot e^{iD_{B,i}}, \end{equation} where $D_{B,i}$ is $i$th element of the diagonal matrix $D_B$, i.e. $i$th eigenvalue, and I used the fact that $\langle{j}\rvert e^{iD_B} \lvert{i}\rangle = 0$ if $j \neq i$. Since $X$ is a unitary operator, we can absorb it to the exponent, i.e. $X^* e^{iD_A}X = e^{iX^*D_AX}$. Moreover, applying $X^*$ and $X$ to $D_A$ won't change the eigenvalues (diagonal elements) of $D_A$, but permutes the ordering of diagonal elements of $D_A$. Denoting this permutation by $p(i)$, we finally have
\begin{equation} = \sum_i e^{iD_{A,p(i)}}\cdot e^{iD_{B,i}}. \end{equation}
However, numerics tell me that my equation is wrong. What am I missing here?
One thing that certainly makes this confusing is that you're mixing bra-ket notation (coordinate free/basis independent) with matrix representations (basis dependent notation). It doesn't really make sense to "diagonalize" when using bra-ket notation, just use the eigen-basis to calculate the trace.
Assuming $B$ is a self adjoint operator, it seems like what you want is to say that $\{\lvert i\rangle\}$ is the eigen-basis of $B$, i.e. $B\lvert i\rangle=\lambda_i\lvert i \rangle$. In which case
$$\langle m \lvert e^{iB}\rvert n\rangle=\delta_{mn}e^{i\lambda_n}$$
Then your trace becomes
$$\begin{align} \text{Tr}\left(e^{iA}e^{iB}\right)&=\sum\limits_{i,j}\langle i \lvert e^{iA}\rvert j\rangle \langle j \lvert e^{iB}\rvert i\rangle\\ &=\sum\limits_j \langle j \lvert e^{iA}\rvert j\rangle e^{i\lambda_j} \end{align}$$
Notice that we don't know anything about $\langle j \lvert e^{iA}\rvert j\rangle$ since the eigen-basis we chose was that of $B$ not of $A$. So unless $A$ and $B$ commute (in which case they share an orthonormal eigen-basis and $e^{iA} e^{iB}=e^{i(A+B)}$) then the expression cannot simplify any further until the action of $A$ on the eigen-basis of $B$ is specified.
In your attempt one thing that was incorrect was that you said that applying $X^*$ and $X$ on $D_A$ would permute the eigenvalues, this is incorrect in general $X^* D_A X$ need not be diagonal at all.
Hope this helps