Nexus 7 5.1.1 - Confirmed internet access, however Google Play store downloads hang forever

[afod179]

My nexus 7 has internet access (over WiFi). However all updates or downloads through Google Play hang indefinitely.

I have tried rebooting, and system cache partition wipe.

Any help would be appreciated.