After running the toombstone recovery rake task and then the fix_missing_uploads rake task, I finally got it to start “fix” the images.
It seems like it’s downloading them and uploading them again, and it takes a lot of time and uses a lot of resources, but at the least the users will get their images back!
Thank you for the help @pfaffman 