We investigate the scattering of surface electrons by the edges of graphene islands grown on Ni(111). By combining local tunneling spectroscopy and ab initio electronic structure calculations we find that the hybridization between graphene and Ni states results in strongly reflecting graphene edges. Quantum interference patterns formed around the islands reveal a spin-dependent scattering of the Shockley bands of Ni, which we attribute to their distinct coupling to bulk states. Moreover, we find a strong dependence of the scattering amplitude on the atomic structure of the edges, depending on the orbital character and energy of the surface states.