Had this same problem which turned out to be a Firewall problem between the built-in windows firewall and Bitdefender Internet Security 2015. I had to uninstall bitdefender, reboot, re-install bitdefender, reboot, and now the store updates properly.
A few days ago I got a popup from Windows 10's Security and Maintenance that there was a problem with the firewall. This took me to Windows Firewall that showed the firewall was off. If you have some other firewall installed, do NOT turn the windows firewall back on.
If you have both the windows firewall and some other firewall on, you can try turning off the windows firewall. But this didn't work for me, even with reboots.