I was deeply puzzled this afternoon, when I configured my App Catalogue and all was fine - except I was unable to access the SharePoint Store.

"Sorry we can't seem to connect to the SharePoint store"

hmm..  checked network, DNS, proxy, certificates, App/System Logs, ULS logs.. nothing....   then it clicked!

Dive into Central Admin->Manage Web Applications,
select the web-application and up in the Ribbon, select Manage Features
now ACTIVATE for internet access to the Store!

"Apps that require accessible internet facing endpoints"
"Allow users to acquire apps that require internet facing"
"endpoints from the SharePoint Store."

IISRESET and voila! everything works fine.

whew!