It is obvious that $B = OAO^\dagger$ have equal trace if $O$ is Hermian. But is is also so that:
$Tr(A) = Tr(B) \rightarrow A = OBO^\dagger$
For some Hermitian $O$ ?
I know this should be trivial to prove/disprove but Is just can't get it sorted out...
I think that you meant that $O$ is unitary, and that $A$ and $B$ are Hermitian. If that's the case, your statement is not true.
Note that $OAO^\dagger$ has the same eigenvalues as $A$. If we take $$ A = \pmatrix{1&0\\0&1}, \quad B = \pmatrix{2&0\\0&0} $$ Then we see that $\operatorname{tr}(A) = \operatorname{tr}(B)$. Since they have different eigenvalues, however, there can be no unitary $O$ such that $B = OAO^\dagger$.