Under what conditions do the phase margin and Nyquist criteria give the same results? When designing feedback systems, I often evaluate stability by thinking about phase margin: the closed loop system $$T(s) = \frac{L(s)}{1+L(s)}$$ is stable if $L(s)$ has positive phase margin, i.e., 
$$\angle L(j\omega) &gt; -\pi/2$$ at all frequencies for which $$|L(j\omega)|&gt;1$$. This is easy to visualize graphically using a Bode plot. 

But for some systems -- typically involving right-half-plane poles and/or zeros in $L(s)$ -- this criterion doesn't work and we need to use the Nyquist criterion to check stability. That is, the number of unstable closed-loop poles is equal to the number of encirclements of $-1+j0$ by the polar plot of $L(s)$ when $s$ is evaluated along an appropriate contour. My understanding is that this Nyquist criterion is more general, and the "positive phase margin" rule is a simplification that only applies in certain cases. 

I'm looking for a criterion that will let me decide when these two criteria (positive phase margin and the Nyquist test) will give me the same results. I suspect that it involves right-half-plane poles and/or zeros in $L(s)$, but I'm not sure.
As you have pointed out, the nyquist stability criterion is more general, moreover, is the only stability criterion. Nevertheless, the Bode plot give us the exact same information that the nyquist plot does, so the stability of a system can be determined with either the bode or the nyquist plot, some times its easier with the former and other times with the latter. for minimum phase system this is usually easier with the bode plot, since you only have to see that (as you said) $$\angle L(j\omega) &gt; -\pi/2 $$
at all frequencies for which
$$|L(j\omega)| &gt; 1 $$

Answering your question explicitly, this is only valid for minimum phase systems. For systems that are not minimun phase the gain and phase margins are not as straightfoward to find.