Activation Error updating to iOS 7.0.4

After working on this for the last few hours, I am exhausted and frustrated.

I'm trying to upgrade my dad's iPhone 4 from iOS 5 to the latest version of iOS 7. I was trying to do it from his PC at first, but between trying to get his computer to actually recognize his iPhone and error messages over and over, I just decided to do it from my MBP.

His Phone was backed up and already put into recovery mode because it got halfway through activation before being interrupted by an error. I connected via USB to my MBP and clicked restore... good news was that it did at least get upgraded to iOS 7, but now I'm getting the error in iTunes

We're sorry, we are unable to continue with your activation at this time.
Please try again later, or contact customer care.

and the same on his Phone as it tries to go through setup.

I'm seeing a bunch of people with this issue during the iOS 7 beta, but none recently. Anyone know a fix for this?
It says contact customer care but I'm not sure if I'm supposed to contact Apple or Verizon.

Thanks.

 

Armen, thanks for the tip. Unfortunately, it's been done and I'm not sure downgrading is an option. It was really about trying to see if we could get his iPhone 4 viable and compatible with the apps that he wants to use. Unless I can get it working now, it's looking like we might just have to upgrade his hardware..

 

Okay, went to the Apple Store today. They told me that I needed to call Verizon as well. Still somewhat frustrated as upgrading iOS7 has been killing off all my devices left and right and then I am being asked to pay out of warranty for replacements/repair...

 

Wasn't able to reach that through the welcome menu because only emergency call was available. My dad was on the phone with verizon as well and they tried everything. They said the only option was to replace the phone.