Help with NMOS Gate question
Is it because M1, M2 are p-channel and M3, M4 are n-channel.


Yes.

You answered your own question. In fact, you probably meant to say "PMOS" in your question title, since that is the type of transistor gate function you are confused about.

V_threshold is a physical concept

To keep it simple, just consider the source and the gate. The threshold voltage is defined as the difference between them. When they are different, mobile charges are attracted into the channel and it becomes conductive (e.g. "on"). Without a difference in gate and source voltages, mobile charges stay away (the depletion region) and the channel is not conductive as a result (e.g. "off").

With v1, v2 = 0, The sources are near VDD, but the gates are 0. That creates a big difference between source and gate for the PMOS -- so they are "on". 

but for the NMOS, the sources are 0 so with the gates also 0, there is no difference and the NMOS channels are "off".