"Complex sampling" can break Nyquist? I have heard anecdotaly that sampling complex signals need not follow Nyquist sampling rates but can actually be gotten away with half Nyquist sampling rates. I am wondering if there is any truth to this?

From Nyquist, we know that to unambiguously sample a signal, we need to sample at least higher than double the bandwidth of that signal. (I am defining bandwidth here as they do in the wiki link, aka, the occupancy of the positive frequency). In other words, if my signal exists from -B to B, I need to sample at least > 2*B to satisfy nyquist. If I mixed this signal up to fc, and wished to do bandpass sampling, I would need to sample at least > 4*B.

This is all great for real signals. 

My question is, is there any truth to the statement that a complex baseband signal (aka, one that only exists on one side of the frequency spectrum) need not be sampled at a rate of at least > 2*B, but can in fact be adequately sampled at a rate of at least > B? 

(I tend to think that if this is the case this is simply semantics, because you still have to take two samples (one real and one imaginary) per sample time in order to completely represent the rotating phasor, thereby strictly still following Nyquist...)

What are your thoughts?
Your understanding is correct. If you sample at rate $f_s$, then with real samples only, you can unambiguously represent frequency content in the region $[0, \frac{f_s}{2})$ (although the caveat that allows bandpass sampling still applies). No additional information can be held in the other half of the spectrum when the samples are real, because real signals exhibit conjugate symmetry in the frequency domain; if your signal is real and you know its spectrum from $0$ to $\frac{f_s}{2}$, then you can trivially conclude what the other half of its spectrum is.

There is no such restriction for complex signals, so a complex signal sampled at rate $f_s$ can unambiguously contain content from $-\frac{f_s}{2}$ to $\frac{f_s}{2}$ (for a total bandwidth of $f_s$). As you noted, however, there's not an inherent efficiency improvement to be made here, as each complex sample contains two components (real and imaginary), so while you require half as many samples, each requires twice the amount of data storage, which cancels out any immediate benefit. Complex signals are often used in signal processing, however, where you have problems that map well to that structure (such as in quadrature communications systems).