We're unable to connect to the Marketplace

Whenever I try to connect to the Marketplace, I get the error "We're unable to connect to the Marketplace. Maybe check your Internet Connection?".

 

My Internet connection is fine, works with all other apps including the windows marketplace.

I have disabled all security software and the issue still remains.

It is preventing me purchasing anything from the store at all.