We report on the detection of the CO(4-3) line with the IRAM Plateau de Bure Interferometer in two z>3 radio galaxies, doubling the number of successful detections in such objects. A comparison of the CO and Ly-alpha velocity profiles indicates that in at least half of the cases, the CO is coincident in velocity with associated HI absorption seen against the Ly-alpha emission. This strongly suggests that the CO and HI originate from the same gas reservoir, and could explain the observed redshift differences between the optical narrow emission lines and the CO. The CO emission traces a mass of H_2 100-1000 times larger than the HI and HII mass traced by Ly-alpha, providing sufficient gas to supply the massive starbursts suggested by their strong thermal dust emission.