We present high-resolution (R ~ 60,000) optical spectra of a carefully selected sample of heavily obscured and presumably massive O-rich asymptotic giant branch (AGB) stars in the Magellanic Clouds. We report the discovery of strong Rb I lines at 7800 Å in four Rb-rich LMC stars at luminosities equal to or greater than the standard adopted luminosity limit for AGB stars (M bol ~ -7.1), confirming that "hot bottom burning" may produce a flux excess in the more massive AGB stars. In the SMC sample, just one of the five stars with M bol < -7.1 was detected in Rb; the other stars may be massive red supergiants. The Rb-rich LMC AGB stars might have stellar masses of at least ~6-7 M sun. Our abundance analyses show that these Rb-rich stars are extremely enriched in Rb by up to 103-105 times solar but seem to have only mild Zr enhancements. The high Rb/Zr ratios, if real, represent a severe problem for the s-process, even if the 22Ne source is operational as expected for massive AGB stars; it is not possible to synthesize copious amounts of Rb without also overproducing Zr. The solution to the problem may lie with an incomplete present understanding of the atmospheres of luminous AGB stars.