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.
See e.g. 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.