Using NOEMA and ALMA 3mm line scans, we measured spectroscopic redshifts of six new dusty galaxies at 3.5 < z < 4.2 by solidly detecting CI and CO transitions. The sample was selected from the COSMOS and GOODS-North super-deblended catalogs with far- infrared (FIR) photometric redshifts z$_phot$ > 6 based on template IR spectral energy distribution (SED) from known submillimeter galaxies at z = 4-6. Dust SED analyses explain the z$_phot$ overestimate from seemingly cold dust temperatures (T$_d$) and steep Rayleigh-Jeans (RJ) slopes, providing additional examples of cold dusty galaxies impacted by the cosmic microwave background (CMB). We therefore studied the general properties of the enlarged sample of 10 ``cold’’ dusty galaxies over 3.5 < z < 6. We conclude that these galaxies are deceivingly cold at the surface but are actually warm in their starbursting cores. Several lines of evidence support this scenario: (1) The high infrared surface density ensuremathΣ$_IR$ and cold T$_d$ from optically thin models appear to violate the Stefan-Boltzmann law; (2) the gas masses derived from optically thin dust masses are inconsistent with estimates from dynamics and CI luminosities; (3) the implied high star formation efficiencies would conflict with cold T$_d$; and (4) high FIR optical depth is implied even using the lower, optically thick dust masses. This work confirms the existence of a substantial population of deceivingly cold, compact dusty starburst galaxies at z ensuremathgtrsim 4, together with the severe impact of the CMB on their RJ observables, paving the way for the diagnostics of optically thick dust in the early Universe. Conventional gas mass estimates based on RJ dust continuum luminosities implicitly assume an optically thin case, which leads to overestimation of gas masses by a factor of 2-3 on average in compact dusty star-forming galaxies.