I will contact Telus and Samsung about this, now that you have confirmed that it is not just my phone, but a bug in ICS for the SIIX.
The interesting thing is that the voice Web search works perfectly well (better than with Gingerbread) and Voice Talk for calling, texting, etc, works perfectly well also.
I don't often use voice to search the Play Store, so it is no big deal, but it is disappointing that such a glaring issue would get released to public. It's not like there was a spelling error in a sub menu, it is an in your face feature that people are going to use (or not
Thanks for the confirmation!