I got lucky, I took out the SIM card (but connected via Wi-Fi), set the date and time manually. Let it sit for 10-30 minutes, then set it back to "Set date and time automatically", again let it sit 10-30 minutes then check for an update.
Only then the update came down. After it was installed I put the SIM back in.
I'll give that a try over the weekend when I have some time. Not going to hold my breath on it since nothing else has worked, but it certainly can't be any worse than what I've already tried.