Ok guys I have an S4 and after a couple hours I found the problem. It's not Google Now you need...it's just GOOGLE. Make sure it is ENABLED on your phone. Search Google on the Google Play store, enable it, do the update, and everything should be working!