Ok update for whoever may have this problem in the future:
I've reinstalled the base 2008 firmware using the desktop application and then immediately did the over-the-air update. It worked.

I consider this problem closed. I'm not thrilled I had to do it this way but it worked.