I’ve been fighting with this damned error after upgrading more than one Mac (in general from 10.6 to 10.7 or 10.8). OS upgrade was ok, but then no access to further upgrades, nor to the App Store (the system was claiming that I had no Internet connection, which was obviously false…).
Chasing for a solution on google was not easy, but finally I found one. In essence, it was a problem with certificates. The solution was to go to the keychain, and fix all the System Certificates by resetting them to the default (a rather lengthy and boring operation). Moreover, a trick was needed to successfully perform the operation… It wasn’t until I found this video that I could succeed… But I finally did. So, this video was a real lifesaver!