Voice search failing on Nexus 6

It's been quite a while since I used voiced search on my Nexus 6. Ever since I got the Moto 360 I've not really had a need to say "OK Google" to my phone because I could simply say it to my wrist. Today though, because I wanted to quickly look something up and my phone was to hand, I spoke to it and got this:

Brilliant.

I've been here before. I had exactly this sort of problem with my Xperia Z at one point. The problem appeared to go away eventually (actually, it sort of came and went a few times over a matter of weeks, if I recall correctly), although I never really got to the bottom of the cause.

I've tried rebooting the phone and that hasn't helped at all. While it's more of a vague annoyance than anything else (like I say above, my Android Wear device is my goto tool for talking to Google these days) it does frustrate a little when fairly expensive tools don't "just work".