Are you using .NET or Java Web Services? Uploading a binary as an attachment is supported for Java Web Services, but not in .NET Web Services. In a .NET environment, uploading as a Base-64-encoded string is the supported option.
See the Web Services samples in <Rhythmyxroot>/WebServices/<version>/sample/loader for examples of supported implementations.