OK Google won;t work when phone locked

I have OK google enabled, and I have it set to allow me to use it when phone is locked, and it WAS working fine.
Then it randomly kept NOT working from lock screen and I had to unlock phone, now this problem has become permanent.
I used to find that the settings had somehow become disabled by themselves, and I had to keep re-enabling them, but this is no longer the case, they are enabled whenever I check. I have disabled and enabled the settings to no avail.
Phone is running Android 5.1