This question requires a careful modification, so that one would be able to speak about the complexity of a solution.
Suppose you have an algorithm that guaranties to run in time $<f(n)$, i.e. makes no more than $f(n)$ queries to the oracle $U$. And it's required it should output an answer with the error probability no more than $1/3$.
It doesn't matter how big $f(n)$ is, there is always a state $|\psi\rangle$ which is very close to the boundary of the set of entangled states. For such a state your algorithm won't be able to decide with the error less than 1/3.
In other words, the time bound $f(n)$ can't be independent of $|\psi\rangle$.
A natural modification would be to consider a weak membership problem. That is, if $|\psi\rangle$ is within the Euclidean distance $\beta > 0$ from the boundary of the set of entangled states. This is what is done in https://arxiv.org/abs/0810.4507.
But even this modification is not enough to fall into a bound error complexity class.
The problem is that we can never be completely sure about any of the properties of $|\psi\rangle$, unless we also restrict the set of possible $U$ in consideration.