I have a matrix $U \in U(n)$ ($U^* U=Id$), with eigenvalues $\lambda_1, \dots \lambda_n \in S^1$. I would like to know if its always possible to find a matrix $O \in O(n)$ such that the eigenvalues $\lambda^{'}_1, \dots, \lambda^{'}_n$ of $UO \in U(n)$ can be written as: $$\lambda^{'}_j=e^{i \pi \alpha_j}$$ Where $\alpha_j \in [0,1)$.
There is an easy case. If $U$ is a diagonal matrix and $J \subset \{1, \dots , n \}$ is the subset such that for $j \in J$ we have $\lambda_j=x_j + iy_j$ with $x,y \in \mathbb{R}$ and $(y<0 \vee x=-1)$. Then choosing:
$$\{O\}_{mn}=\begin{cases}
0 & m\ne n \\
-1 & m=n\in J \\
1 & else
\end{cases}$$
This will define an orthogonal matrix and $UO$ will be as desired.
The problem is that when $U$ is not a diagonal matrix the matrix $S=P^*OP$ for $P \in U(n)$ and $O \in O(n)$ is not generally an orthogonal matrix so there is no simple algorithm as far as I can see to find $O \in O(n)$
This is not exactly what you asked but it might help to solve this or narrow the search for a counter example.
We have $U \in U(n) \implies spec(U)\subset S^1$. $spec(U)$ is discrete and therfore any function on it is continuous. Define $f:spec(U) \to \{-1,1\}$ $$e^{i\pi \theta} \mapsto \begin{cases} 1 & \theta \in [0,\pi) \\ -1 & \theta \in [\pi,2\pi) \end{cases}$$ Note that $\bar{f}f=f^2=1$. Set $O=f(U)$. Since $f$ has image in $\mathbb{R}\cap S^1$ then $$O \in U(n)\cap H(n)$$ Moreover, for all $x \in Spec(U)$: $$\overline{xf(x)}xf(x)=1$$ so $(UO)^*(UO)=I$ because the continuous functional calculus is a $C^*$ algebra homomrphisim. Finally $xf(x) \in S^1 \cap \mathbb{H}$ and therefor $UO$ has spectrum in $S^1 \cap \mathbb{H}$. $U(n) \cap H(n)$ has similar properties to the orthogonal group so this might help.