I know this post is a little old. But, there really isn't a lot of results for this issue. I was having this same problem. It just happened out of the blue. I tried clearing the cache in the Google app, I tried installing the Google Now Launcher (I always use Nova Launcher), and a ton of other junk. What fixed it for me was to go into the Google app, tap on the three slashes in the upper left hand corner for settings, opened up the option for my account (*******@gmail.com), and then I chose the option to sign out of my account. Upon signing back into my Google account okay Google started working again. Hope this helps.