Error Sending A Binary Object To A Web Service

I need to pass a block of binary data to a web service. The object I'm passing is part of an API, so the Serialize/Deserialize/Byte functions are built-in to the API class. It is not explicitly XML Serializable as far as I can tell.

Unfortunately, whenever I pass the data to my web service, even as an encoded string, the service returns a "(400) Bad Request" error. If I remove the encoded data and replace the variable with a simple string, an appropriate response is returned, ruling out authentication, service errors, etc.

'Convert the byte array into an encoded string'
Dim unicodeEncoder As New UnicodeEncoding()
Dim serializedData As String = unicodeEncoder.GetString(myObject.Bytes).Trim()
Dim webAuth As New myWebService.ServiceSoapClient
MessageBox.Show(webAuth.VerifyFeatureSet(serializedData , "", "", "", ""))

how I can accomplish this? If I need to encode the data a different way, include a snippet for decoding it on the far end.