Okay, my next recommendation would be a cache wipe in recovery (or a factory reset). You, of course, could always take your phone into the carrier's store too.
[INFO]Cache wipe:
1. Make sure you're in a location where you have a wifi connection. (Some updates only download via wifi)
2. Boot into recovery. I don't own a S3, so I'm not sure the specific way to do it, but it generally involves holding down certain buttons on boot-up. Often, a Google search for "boot [phone model] to recovery" will get your answer for you.
3. Clear the cache partition. This is like a "temp" directory on your Android system, and is also where the updates are downloaded to for staging. If you have a corrupt update download mucking things up, this will remove it. Wiping the cache will NOT remove any user apps or data, and is generally a pretty harmless procedure.
4. Reboot the phone normally.
[/INFO]