Did you use "Voice Search" or "Voice Dialer" (not sure what is the difference, but I always use voice Dialer for...erm...voice dialing lol)

Anyway, sometimes it may be due to Asians pronunciation which is different

Try Vlingo from market if you really need the voice dialing function