Message: This Apple ID has not yet been used with the app store I've set up billing information and address but still the laptop I am trying to use says "This Apple ID has not yet been used with the app store."

I am entering in my information correctly. Because I get to that screen.

I just updated billing and address about 10 minutes ago but the laptop doesn't seem to have registered that.
I also have face this issues but in my case I have created the Apple ID through web on linux and when I got the Mac and try to use this to download the Xcode for installation after entering the correct credential it pop up the this message. 
After googling I come to know that billing or shipping is not configure in account I have enter the all detail but still I was facing this issues.

So I have solve this by clicking in the iTunes(icon of music tune) in Mac/mobile and enter the same(your created Apple ID and password) credential and follow the next steps on the go.

Here You go to payment and billing section and select the option None as payment mode and then add the your address and save it,
This you can do from web if you don't want buy any app if want buy then you need to select payment mode and enter the payment detail.

and then I click on the App Store to try to install by clicking the free software and click on get and install app then pop will come to ask for the Apple ID and password now enter the same credential one more popup will come "ask password every time" so click on the alway ask password and you done