Graphene has emerged as a versatile material with outstanding electronic properties(1-4) that could prove useful in many device applications. Recently, the demonstration of spin injection into graphene and the observation of long spin relaxation times and lengths have suggested that graphene could play a role in 'spintronic' devices that manipulate electron spin rather than charge(5-8). In particular it has been found that zigzag graphene nanoribbons have magnetic (or spin) states at their edges, and that these states can be either antiparallel or parallel(9-16). Here we report the results of first-principles simulations that predict that spin-valve devices based on graphene nanoribbons will exhibit magnetoresistance values that are thousands of times higher than previously reported experimental values(17-19). These remarkable values can be linked to the unique symmetry of the band structure in the nanoribbons. We also show that it is possible to manipulate the band structure of the nanoribbons to generate highly spin-polarized currents.