This alone didn't work on my Note 8.0. I first had to do the following:
Settings> Date Usage> GooglePlay on the bottom uncheck "Restrict background data", then go to Settings> Applications> GooglePlay Service> Force Stop> Clear Data. Then reboot.
Then GooglePlay was back as normal.