As @TsuyoshiIto suggests, there is an $O(n\log n)$-time algorithm for this problem, due to Edelsbrunner and Preparata. In fact, their algorithm finds a convex polygon with the minimum possible number of edges that separates the two point sets. They also prove an $\Omega(n\log n)$ lower bound for the more general problem in the algebraic decision tree model; however, it's not clear whether this lower bound applies to the triangle case.
A full description of the algorithm is too long to post here, but here's the basic idea. Let $C$ be the convex hull of the positive points. For each negative point $q$, consider the lines through $q$ that are tangent to $C$. These lines split the plane into four wedges, one of which contains $C$; let $W(q)$ be the wedge opposite the one that contains $C$. Finally, let $F$ (the "forbidden region") be the union of all wedges $W(q)$. Any separating triangle must separate $C$ from $F$. Both $C$ and $F$ can be constructed in $O(n\log n)$ time.
Label the edges of $F$ alternately clockwise and counterclockwise. Edelsbrunner and Preparata further prove that if a separating triangle exists, then there is a separating triangle whose edges are collinear with clockwise edges of $F$. In $O(n)$ additional time, we can find the (necessarily clockwise) edge of $F$ first hit by a ray from each clockwise edge $e$; call this edge the "successor" of $e$. The successor pointers partition the clockwise edges into cycles; if there is a separating triangle, one of these successor cycles has length 3 (and none have length more than 4).
See the original paper for more details: