I can't connect my phone to the iTunes Store which means I can't upgrade any of my apps or download new ones

You've tried logging out of your account on your phone and logging back in to see if that fixes it ?

If it doesn't then try closing the App Store app via the phone's multitasking bar : from the phone's homescreen (i.e. not with the App Store app 'open' on-screen) double-click the home button to bring up the taskbar, then press and hold any of the apps on the taskbar for a couple of seconds or so until they start shaking, press the '-' in the top left of the App Store app to close it, and touch any part of the screen above the taskbar so as to stop the shaking and close the taskbar.

Also do a soft-reset (i.e. a reboot) and see if you can : press and hold both the sleep and home buttons for about 10 to 15 seconds (ignore the red slider), after which the Apple logo should appear (you won't lose any content).

Then see if the App Store app can connect.

I did a power-off and after rebooting my iPhone5, syncing is happening now.