For speech recognition to work on Android, you need to enable the forwarding on your firewall of the 19294 tcp port.

References: http://code.google.com/support/bin/answer.py?answer=62464