We explore the phase diagram of neutral quark matter at high baryon density as a function of the temperature T and the strange quark mass Ms. At T=0, there is a sharp distinction between the insulating color-flavor locked (CFL) phase, which occurs where Ms^2/mu < 2 Delta, and the metallic gapless CFL phase, which occurs at larger Ms^2/mu. Here, mu is the chemical potential for quark number and Delta is the gap in the CFL phase. We find this distinction blurred at nonzero T, as the CFL phase undergoes an insulator-to-metal crossover when it is heated. We present an analytic treatment of this crossover. At higher temperatures, we map out the phase transition lines at which the gap parameters Delta_1, Delta_2 and Delta_3 describing ds-pairing, us-pairing and ud-pairing respectively, go to zero in an NJL model. For small values of Ms^2/mu, we find that Delta_2 vanishes first, then Delta_1, then Delta_3. We find agreement with a previous Ginzburg-Landau analysis of the form of these transitions and find quantitative agreement with results obtained in full QCD at asymptotic density for ratios of coefficients in the Ginzburg-Landau potential. At larger Ms^2/mu, we find that Delta_1 vanishes first, then Delta_2, then Delta_3. Hence, we find a "doubly critical'' point in the (Ms^2/mu,T)-plane at which two lines of second order phase transitions (Delta_1->0 and Delta_2->0) cross. Because we do not make any small-Ms approximation, if we choose a relatively strong coupling leading to large gap parameters, we are able to pursue the analysis of the phase diagram all the way up to such large values of Ms that there are no strange quarks present.

24 pages; 22 figures; typos in labelling of Figs. 7, 20 corrected