Simulations of surface chemistry often use density functional theory with generalized gradient approximations (GGAs) for the exchange-correlation functional. GGAs have well-known limitations for gas-phase chemistry, including underestimated reaction barriers, and are largely superseded by meta-GGAs and hybrids. Our simulations of O and Li adatoms on graphene add to a growing body of evidence that GGAs have similar limitations on surfaces and that meta-GGAs and screened hybrids are computationally feasible for such systems. Meta-GGAs and screened hybrids systematically improve accuracy, just as they do for gas-phase chemistry, motivating their continued exploration in surface chemistry.