Mine stopped working a few days ago, too. Motorola Razr HD, android 4.0.4. It repports "Server Problem" and gives a very annoying piercing "Dah-DAH" sound.
The only place it doesn't work is on the Home screen, when I click the microphone in the Google search bar widget (permanent on Android 4.0.4). The voice search works fine from the various keyboard microphones.
Wished I hadn't of messed with my Contacts list, others seem to associate that with this "Server Problem".
Things I have tried:
Searching Google Help forums
Rebooting phone
turning off Google email syncing
changing keyboard, locale, language and Input settings.