Okay, this is just stupid. The only thing I did not restore was the browser because I apparently deleted it somehow...
Does anyone have a Titanium Backup copy of the browser they can send me?
I think I'm going to call Verizon and let them send me another phone because I just got this thing. This is the same error I got on the other phone for the first update - IP_PREVIOUS_UPDATE_FAILED.
I've restored everything, I've even performed the dreaded factory reset and I got nothing. Oh well, time to spend an hour or so on the phone so I can get this thing replaced.