I think the voice search "server problem" issue is due to a conflict between Google Contacts, Google+ Circles, and the Contacts displayed on our phones. I had the same issue on my GSM Galaxy Nexus 4.0.2 (yakju) but now I am able to keep my contacts sync'd while performing voice searches**.
Below are the steps I used to narrow down the issue which resulted in a fix:
1) Enable sync on your phone for everything including contacts: Settings --> Accounts & Sync --> select your account --> check all the boxes. Stay on that screen and force a sync by selecting Sync Now.
2) On a computer, delete all contacts from within your Gmail Contacts screen: Gmail --> Contacts --> select all contacts via the topmost check-box --> More --> Delete Contacts. (You can either export your contacts first to back them up or rely on the Restore feature as I did below.)
3) Force a sync on your phone: Settings --> Accounts & Sync --> select your account --> Sync Now. After syncing with your phone, the phone Contacts will display 0 contacts. (I still couldn't perform a voice search at this point.)
4) In the Google Plus app on your phone, enable/check "Sync Contacts": Google+ --> Settings --> Phone Contacts --> check sync contacts. Now the people in your Google+ circles will now be displayed under a separate "Google+" heading in Contacts on the phone. At this point when you go to Contacts on your phone, you should have 0 contacts under the "Google" heading and some number of Google+ contacts under the Google+ heading.
5) Go to your Google+ Circles on a computer and remove all people from your circles. Force another sync, and your phone Contacts should display 0 contacts under the "Google" heading and 0 contacts under the "Google+" heading.
6) Try voice search. At this point I could do voice search commands. Yay!
7) Go back to Gmail Contacts on your computer, and under More you can either select Restore with an appropriate restore point (which is what I did) or import your exported contacts. After forcing another sync I could still do voice search commands.
8) Go to Google+ on your computer and add people back to your Circles. After forcing another sync I could still do voice search commands.
It is possible if I had just sync'd contacts via the Google+ app on my phone this issue would have been resolved without going through the steps to delete everything, or perhaps just removing people from my Google+ Circles would have done the trick.
----------
**I can now do voice commands for internet searches, maps, navigation, "listen to", etc., however, I cannot do a voice search command involving contacts. The lack of voice commands involving contacts seems to be an issue people experience without experiencing our server problem issue so this may be better suited for a separate issue entry.
For example, if I try to say "send email to dad don't forget to send flowers to mom for valentine's day", the voice email prompt will pop up but instead of listing:
//To: Dad
//Message: don't forget to send flowers to mom for valentine's day
The phone will list:
//To: [blank]
//Message: to dad don't forget to send flowers to mom for valentine's day
So the voice search recognizes my spoken input but it will not search my contacts for my Dad entry, instead putting my spoken phrase into the "Message" field after it recognizes my command "send email". Additionally, in that same prompt, if I manually click inside the "To:" field and try to use my voice to say "Dad" or any other name in my contacts list the phone will only output the word "test" in the "To:" field.
And now my mom won't get flowers. Thanks, Google. </3
