Danske bogstaver fra webservice

Vi er igang med et mobil-projekt hvor vi laver en J2ME-klient til Microsofts Mappoint-service.
Vi har lavet en webservice som aggerer facade mod mappoint for at minimere antallet af GPRS-kald.
Denne webservice er skrevet i C# og sender SOAP tilbage til J2ME-klienten som parser det og bruger data'en.

Problemet er, at når webservicen sender strenge tilbage via SOAP, så er æ, ø og å blevet ulæselige (læs: forkert encoding).

Vi aner bare ikke hvordan dette skal sættes i vores webservice, for at returnere æøå rigtigt.
Er der nogen der har haft dette problem før?

PS: jeg ved ikke om det har med C# eller SOAP generelt at gøre!