Can't connect to iTunes store or App store - various error and server messages.

What I'm using:

• MBP 13" retina, early 2013
• OSX 10.8.3
• iTunes 11.0.4
• My last nerve

The problem:

• iTunes cannot connect to the iTunes store. Error messages include
  • "iTunes can't verify of the identity of the servier init.itunes.apple.com. The certificate for this server is invalid. You might be connecting to a server that is pretending to be “itunes.apple.com”, which could put your confidential information at risk. Would you like to connect to the server anyway?" Sometimes the server is init.itunes.apple.com.
  • "'We could not complete your iTunes store request. Error (-9807)"
  • They pop up one after the other.
• The App Store cannot connect to the internet

  When I go to the App store, it just stalls and eventually says that it can't connect to the internet.

What I've tried:

• All the "Advanced iTunes Store Troubleshooting" solutions on the Apple Support page: Nothing worked
• The Genius bar: My 'Genius' said he didn't really know what the problems was; that it would be like finding a needle in a haystack.
• Apple forums: I've found plenty of other similar issues, but no solutions...so far.
• Sacrificial rituals to the Dieties of Smooth Functioning MBPs: You guessed it, so far nothing...

Other information:

• This is not an internet/connectivity problem. The problem has reproduced itself consistently for the last month across dozens of networks and three countries. No other connectivity problems.
• I recently purchased this MBP and migrated from my old MBP using Time Machine. This problem has happened from the beginning. No other problems with the migration.
• All my date and time settings are up to date. Update automatically is turned off.
• I'm doing this from South Sudan, so going into a store is not an option and calling is quite difficult.

Any help would be greatly appreciated. I'm largely non-technical – only under duress – so simple instructions appreciated!

Thanks very much!