In neutral cold quark matter that is so dense that the strange quark mass M-s is unimportant, all three quark flavors pair in a color-flavor locked (CFL) pattern, and all nine fermionic quasiparticles have a gap Delta (or 2Delta). We argue that, as the density decreases (or M-s increases), there is a quantum phase transition (at M-s(2)/muapproximate to2Delta) to a new "gapless CFL phase" in which only seven quasiparticles have a gap. There is still an unbroken U(1)((Q) over tilde) gluon/photon, but, unlike CFL, gapless CFL is a (Q) over tilde conductor with gapless (charged) quasiquarks and a nonzero electron density at zero temperature, so its low energy effective theory and astrophysical properties are qualitatively new. At the transition, the dispersion relations of both gapless quasiparticles are quadratic, but for larger M-s(2)/mu, one becomes conventionally linear while the other remains quadratic, up to tiny corrections.