The feasibility of contemporary gas-grain astrochemical models depends on the availability of accurate kinetics data, in particular, for surface processes. We study the sensitivity of gas-grain chemical models to the energy barrier Ea of the important surface reaction between some of the most abundant species: C and H2 (surface C + surface H2 = surface CH2). We used the gas-grain code ALCHEMIC to model the time-dependent chemical evolution over a 2D grid of densities (nH: 10^{3} - 10^{12}cm^{-3}) and temperatures (T: 10 - 300 K), assuming UV-dark (Av = 20 mag) and partly UV-irradiated (Av = 3 mag) conditions that are typical of the dense interstellar medium. We considered two values for the energy barrier of the surface reaction, Ea = 2500 K (as originally implemented in the networks) and Ea = 0 K (as measured in the laboratory and computed by quantum chemistry simulations). We find that if the C + H2 = CH2 surface reaction is barrierless, a more rapid conversion of the surface carbon atoms into methane ice occurs. Overproduction of the CHn hydrocarbon ices affects the surface formation of more complex hydrocarbons, cyanides and nitriles, and CS-bearing species at low temperatures < 10-15 K. The surface hydrogenation of CO and hence the synthesis of complex (organic) molecules become affected as well. As a result, important species whose abundances may change by more than a factor of two at 1 Myr include atomic carbon, small mono-carbonic (C1) and di-carbonic (C2) hydrocarbons, CO2, CN, HCN, HNC, HNCO, CS, H2CO, H2CS, CH2CO, and CH3OH (in either gas and/or ice). The abundances of key species, CO, H2O, and N2 as well as O, HCO+, N2H+, NH3, NO, and most of the S-bearing molecules, remain almost unaffected. Further accurate laboratory measurements and quantum chemical calculations of the surface reaction barriers will be crucial to improve the accuracy of astrochemical models.