When entering my password into App Store I get:
There was an error connecting to the Apple ID server
I checked the password and it's fine. I changed the password just in case, it still does not work, but now my whole Mac is disconnected from my iCloud account.
When I open Console, I get:
2016-05-01 9:17:06.292 PM com.apple.xpc.launchd[1]: (com.apple.auditd[1047]) Endpoint has been activated through legacy launch(3) APIs. Please switch to XPC or bootstrap_check_in(): com.apple.auditd
2016-05-01 9:17:06.300 PM myusername[1052]: audit warning: soft /var/audit
2016-05-01 9:17:06.300 PM myusername[1053]: audit warning: closefile /var/audit/20160502011137.20160502011706
2016-05-01 9:17:06.300 PM myusername[1051]: audit warning: allsoft
2016-05-01 9:17:06.499 PM akd[300]: NSURLSession/NSURLConnection HTTP load failed (kCFStreamErrorDomainSSL, -9807)
2016-05-01 9:17:06.700 PM akd[300]: NSURLSession/NSURLConnection HTTP load failed (kCFStreamErrorDomainSSL, -9807)
2016-05-01 9:17:06.898 PM akd[300]: NSURLSession/NSURLConnection HTTP load failed (kCFStreamErrorDomainSSL, -9807)
It seems like people get the last error when they're using an iOS 9 app that doesn't support TLS 1.2.
I'm using OS X El Capitan 10.11.4.
Edit: same issue using Safe Boot.
Best Answer
I've had the same problem with App Store and Icloud for some time. For me the root cause for was a security hardening tip to enforce OSCP and CRL verification.
To see if you have the same problem start "Keychain Access" and open "Preferences". Select "Certificates" and verify that you have "Best attempt" for CRL and OCSP. After changing these values back to "Best attempt" I could login to Itunes. I had to restart to be able to login to App Store.