The magnetic compass sense of migratory birds is thought to rely on magnetically sensitive radical pairs formed photochemically in cryptochrome proteins in the retina. An important requirement of this hypothesis is that electron spin relaxation is slow enough for the Earth's magnetic field to have a significant effect on the coherent spin dynamics of the radicals. It is generally assumed that evolutionary pressure has led to protection of the electron spins from irreversible loss of coherence in order that the underlying quantum dynamics can survive in a noisy biological environment. Here, we address this question for a structurally characterized model cryptochrome expected to share many properties with the putative avian receptor protein. To this end we combine all-atom molecular dynamics simulations, Bloch-Redfield relaxation theory and spin dynamics calculations to assess the effects of spin relaxation on the performance of the protein as a compass sensor. Both flavin-tryptophan and flavin-Z˙ radical pairs are studied (Z˙ is a radical with no hyperfine interactions). Relaxation is considered to arise from modulation of hyperfine interactions by librational motions of the radicals and fluctuations in certain dihedral angles. For Arabidopsis thaliana cryptochrome 1 (AtCry1) we find that spin relaxation implies optimal radical pair lifetimes of the order of microseconds, and that flavin-Z˙ pairs are less affected by relaxation than flavin-tryptophan pairs. Our results also demonstrate that spin relaxation in isolated AtCry1 is incompatible with the long coherence times that have been postulated to explain the disruption of the avian magnetic compass sense by weak radiofrequency magnetic fields. We conclude that a cryptochrome sensor in vivo would have to differ dynamically, if not structurally, from isolated AtCry1. Our results clearly mark the limits of the current hypothesis and lead to a better understanding of the operation of radical pair magnetic sensors in noisy biological environments.