Not going to suggest my method of fixing it is universal given how many different solutions are in this thread, but I fixed it by signing into appleid.apple.com and removing the device from my account. It failed to find the update the next time, but after ~3 more retries it eventually worked. Godspeed.