Hi Stef,
I talked to an ESRI analyst at the UC. Though she didn't have a quick and hard solution for us, she did offer some good advice!
Once you have created all your link points, before hitting Update Georeferencing, save the link table. That way, if it doesn't work, at least you can re-load the links when you go back to try it again. She also said that what is causing it is probably some errant pair of points (or link). She said to really pay attention to what is on the link table. If there's a row that's amiss or has an usually high RMS, delete it, then try to update.
If all else fails, just rectify.