We present 12CO 1-0 observations of eleven low luminosity M_B > -18), HI--rich dwarf galaxies. Only the three most metal-rich galaxies, with 12+log(O/H) ~ 8.2, are detected. Very deep CO spectra of six extremely metal-poor systems (12+log(O/H) < 7.5) yield only low upper limits on the CO surface brightness, I_CO < 0.1 K km/s. Three of these six have never before been observed in a CO line, while the others now have much more stringent upper limits. For the very low metallicity galaxy Leo A, we do not confirm a previously reported detection in CO, and the limits are consistent with another recent nondetection. We combine these new observations with data from the literature to form a sample of dwarf galaxies which all have CO observations and measured oxygen abundances. No known galaxies with 12+log(O/H) < 7.9 (Z < 0.1 solar) have been detected in CO. Most of the star-forming galaxies with higher (12+log(O/H) > 8.1) metallicities are detected at similar or higher I_CO surface brightnesses. The data are consistent with a strong dependence of the I_CO/M_H_2 = X_CO conversion factor on ambient metallicity. The strikingly low upper limits on some metal-poor galaxies lead us to predict that the conversion factor is non-linear, increasing sharply below approximately 1/10 of the solar metallicity (12+log(O/H) < 7.9).