"Ok Google" Greyed Out / Unavailable After Hard Reset After Android phone was hard reset to factory settings and restored from backup, inside Google Services Settings, "Ok Google" function was Greyed / Unavailable.

This is even after language selected was English(US) and updated language.

How to solve this issue?
The solution that enabled the "Ok Google" function was to Clear the Storage Data of Google Services Framework.  

Caution, this will invalidate GCM ids of applications that have registered for one.  May require reinstall of those applications.