Ok. Got on chat with support and got it fixed:
1. First I had to fix iTunes. I followed these instructions: http://support.apple.com/kb/TS4123
I was told to uninstall anything in the Winsock list that wasn't my (up-to-date) Antivirus, or something with Microsoft or Apple in the publisher column. In my case it was HMA! Pro VPN and it was also highlighted in red... That fixed iTunes.
(Additional info the support guy sent me that I didn't have to use: http://support.apple.com/kb/TS1814)
2. Then I had to reset my phone using iTunes.
3. Then I had to restore the backup: http://support.apple.com/kb/HT1766
(That didn't work for some reason, so they had me go to add/remove programs, right click apple mobile support, and repair the installation. Then I re-restored my phone and it worked. I had to log out of the app store and log back in and verify my payment info before it would recognise my app purchases.)