Welcome to the forums. It's strange that it didn't start again after restarting the phone. How did you disable it? Try this, go to settings - apps - scroll down until you find Google Play Services - tap on it and then tap on 'app details'. What options do you get on that Pay Store screen?