We propose a deep learning approach for reconstructing undersampled k-space data corrupted by motion. Our algorithm achieves high-quality reconstructions by employing a novel neural network architecture that captures the correlation structure jointly present in the frequency and image spaces. This method provides higher quality reconstructions than techniques employing solely frequency space or solely image space operations. We further characterize the motion severities for which the proposed method is successful. This analysis represents the first step toward fast image reconstruction in the presence of substantial motion, such as in pediatric or fetal imaging.