Don't throw your desktop over the wall just yet. I assume you're using the method described in the first part of My Drawing or Assembly can't find dependent files. to try to update the references? If yes, and it still isn't working, maybe it has something to do with folder permissions? Is there any chance you can get the user who's Documents folder the components got moved to to do a Pack and Go of the Assembly (How can I create a new Assembly or Drawing similar to an existing one?) back to the desired location?
Thank you Glenn! I was hoping to avoid pack'n'go since it only creates more copies, so I went through the guide you shared, and your second method helped a lot. For others:
All of the parts that had wrong references were still loading in the assembly on the computer where the parts were saved, so there was nothing to unsuppress. I opened the Edit Referenced File Locations list from the Open window on one screen and the Documents folder on the other screen. After creating a temporary backup of the assembly (far, far from the offending folder), I deleted every part from Documents that was listed in the references, and then opened up the assembly again with all the parts now missing and used Unsuppress to re-create the correct references. These saved just fine - I'm not sure at this point what caused the difficulty with Edit Referenced File Locations (something something PDM), but I'm not going to go searching for the bug again.