Alright, so I have been googling like crazy.. looking for possible fixes for the Speech to Text/Voice Search issue. So maybe you guys have already found and tried this stuff, but I haven't seen it on here so I'll post what I found.
Here's the first one that I found. It has to do with turning off the Personalization Settings of Google Voice and the voice recognition. I didn't realize that Google actually keeps recordings of your voice on your Google account (online), and uses them to help recognize your voice tendencies. You can actually clear that out online and start fresh! Some claimed that fixed their problem. Link:
Voice search broken after Gingerbread update. - Google Mobile Help
Next, this thread actually has a Google employee and Sprint employee recognizing and acknowledging the problem. The resolution here is that the Google Maps update somehow messed up the Voice Recognition. They removed the update and re-updated Maps in the Market, and claim it fixed the issue. Link:
Google Voice Search "No Speech Heard" error - Google Mobile Help
I did both. I'm hoping when I get in my car tomorrow.. it will be fixed (fingers crossed).