We report on the magnetic coupling between isolated Co atoms as well as small Co islands and Ni(111) mediated by an epitaxial graphene layer. X-ray magnetic circular dichroism and scanning tunneling microscopy combined with density functional theory calculations reveal that Co atoms occupy two distinct adsorption sites, with different magnetic coupling to the underlying Ni(111) surface. We further report a transition from an antiferromagnetic to a ferromagnetic coupling with increasing Co cluster size. Our results highlight the extreme, sensitivity of the exchange interaction mediated by graphene to the adsorption site and to the in-plane coordination of the magnetic atoms.