I find the voice recognition of the Touch very good over a Bluetooth headset. Are you using a headset or the speakphone? Also, you have to get the rhythm right and it helps to add the number category if there's more then one number for the contact. For instance:
"Call Tom (slight pause) mobile" if Tom has both home and mobile numbers.
You could also check which firmware your phone is using. If it's not the latest you can get it updated at the Verizon store.