I have the same problem on two machines. On my (late 2013 iMac) I was able to update to beta 2 from the command line using
sudo softwareupdate -i -a
But after the update I have the same "Cannot connect to the Store. An internet connection is required" message when I open App Store. I have functioning wired and wireless connnections, and I am typing this from this very machine.
Now I will try the fix suggested by kcft above, "Change the trust settings to "Use System Defaults" and the blue plus sign should disappear."
Edit to add: OK, ultimately the "Change the trust settings..." worked, although it was tedious and I have no idea which certificte I changed that made the difference. Also, I am nervous about changing certificate settings when I really don't know what I'm doing. I suspect I actually only needed to change one or two of them, but I changed many. It would be good if someone could figure out the real culprit. There are two culprits --
1) Whatever caused the problem in the first place (for me, I think it was installing beta 1)
2) Which specific certificate(s) are borked, and what is the ideal fix.