I have been looking around for an answer to this question but can't really come up with anything. Given some oracle, $U$, that maps $| 0 \rangle$ to $| \psi \rangle$, is there some algorithm that determines whether $| \psi \rangle$ is entangled or separable?
I think there must be an algorithm for this, but is it in BQP? ($O(poly(N))$ where $N$ is the number of qubits), or is it hard?
At least when the state that you're testing is a mixed state (rather than known to be a pure state), there's been quite a bit of work on this. In 2003, Gurvits showed that the problem is NP hard. There's a more recent result that strengthens the statement. It perhaps doesn't directly answer your question about the quantum complexity, especially as these start from a matrix description of the state rather than just a copy of the state, but is certainly suggestive.
In practice, there are algorithms that work pretty well, such as this one.
You might also like to check out the body of work that Lawrence Ioannou produced during his PhD. It's available on the arxiv.
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.
