I had the same problem. I've read from others that the contacts must be type google, not just phone or facebook. So, I finally got all of my contacts added to my gmail account. Still that didn't seem to help. Recently, I noticed that gmail kept trying to create a "my contacts" group every time I added a new contact. I had been deleting contacts from that group since I didn't want/need it. However, when I tried adding all my contacts back into the "my contacts", now my voice search seems to work. So, does google voice search require the contacts be in gmail and in group "my contacts" to work? Seems so to me. Vlingo worked with my contacts without any of this trouble.
Not 100% sure if that is what fixed it for me. Since I've also been deleting all my contacts, clearing cache, uninstal/reinstall voice search. Everything I could think of to try and get voice search working.