In the last years, ultra-low temperature chemical kinetic experiments have demonstrated that some gas-phase reactions are much faster than previously thought. One example is the reaction between OH and CH3OH, which has been recently found to be accelerated at low temperatures yielding CH3O as main product. This finding opened the question of whether the CH3O observed in the dense core Barnard 1b could be formed by the gas-phase reaction of CH3OH and OH. Several chemical models including this reaction and grain-surface processes have been developed to explain the observed abundance of CH$_3$O with little success. Here we report for the first time rate coefficients for the gas-phase reaction of OH and CH3OH down to a temperature of 22 K, very close to those in cold interstellar clouds. Two independent experimental set-ups based on the supersonic gas expansion technique coupled to the pulsed laser photolysis-laser induced fluorescence technique were used to determine rate coefficients in the temperature range 22-64 K. The temperature dependence obtained in this work can be expressed as k(22-64 K) = (3.6+/-0.1)e-12 (T/ 300)^(-1.0+/-0.2) cm3 molecule-1 s-1. Implementing this expression in a chemical model of a cold dense cloud results in CH3O/CH3OH abundance ratios similar or slightly lower than the value of 3e-3 observed in Barnard 1b. This finding confirms that the gas-phase reaction between OH and CH3OH is an important contributor to the formation of interstellar CH3O. The role of grain-surface processes in the formation of CH3O, although it cannot be fully neglected, remains controversial.