Imagino que vc esteja usando um emulador!
Por curiosidade(em nada tem haver com sua resposta), o emulador que vc está usando é pra qual versão doWindows Mobile?
Sobre o erro: Quando vc referenciou o WebService, vc colocou o endereço do webservice com o endereço IP onde ele está publicado? Se vc referenciar o endereço do WebService com o "localhost" não vai funcionar mesmo, pois o emulador é um "device" independente de sua máquina e ele não vai entender o "locahost".