I think the web service provides a byte stream that is simply base64-encoded data represented as integers instead of chars. I believe that the base64 chars are a subset of ASCII, so you need to convert the byte array to ASCII (i.e. base64 represented as chars), then convert these chars from base64:
var base64AsAscii = Encoding.ASCII.GetString(bytesFromWebService);
var decodedBytes = Convert.FromBase64String(bytesAsAscii);
var text = Encoding.UTF8.GetString(decodedBytes);