I having problems also, like some posters have said its got to be a firmware problem as a new virgin now tv box connects fine but once it updates to latest firmware i cannot access app store as it says cannot connect to internet BUT i can still watch my Now TV subscription so the box is telling porkies.
I'm on Virgin 200mb tried all the solutions given hardwired, reset, changed wifi channels etc etc
Tried hotspot on my 3 mobile thinking it could be my network setup..Nope still no internet
BUT take the bloody thing into work to test and its fine on BT using a 3rd party router
Please sort it Now TV!!!
I fixed mine, it may help others that are scratching their heads as to why it worked before firmware update not touched anything else but now it doesnt work
At home I'm on Virgin, I have a Netgear Super Hub 2 being used as a modem and a Netgear NightHawk 8000 router, I noticed on the router the DNS was NOT set to automatically get from ISP, changed it to get from ISP automatically and now on the NOW Tv box i get 3 green ticks and i can access the app store.