My husband & I are having the same issues on our phones. I, also, tried doing all the updates but nothing helped either. Its becoming annoying. Sprint needs to get on the ball & correct. We have the Samsung Galaxy SII.
I also began getting it yesterday afternoon. I disabled Voice Command, cleared the data and restarted it but i'm still getting the pop up. I searched the issue on the internet and others are reporting it as well. They are saying that it's a Google issue and that Google is looking for a fix but i'm not sure how accurate that info is.
Possible fix I found while searching about the same issue on my phone:
I was getting this error constantly today, so I went to Settings → Applications → All → Voice Command. From there I clicked Force Stop → OK then Clear Data → OK. Then I relaunched the voice command by tapping the microphone button on my Google search widget.
I gave it a shot - hopefully it works, because the issue is kind of annoying!
I tried changing to Google as well but still got the pop up. I went in and disabled Voice Command as I don't use it anyway and have not got the pop up since. Crossing my fingers that it lasts.