I had the exact same problem & your Post Solved It
I was searching frantically for the same problem as yours, & then i stumbled upon this post..
I use swiftkey for typing & when i tried using voice input, it used to show me the same error " Unfortunately, Voice Search has stopped "
So when i read this, i thought, if there is no update, why not uninstalling & reinstalling ??
I Uninstalled the Voice Search App from Play Store & Reinstalled it..
And "tada" it worked..
Im loving the typing by voice now..
Thanks to your question which gave me that ide..
Hope you try the same..!!