After searching for a solution to this all week I finally found a web-service call that works with it. Here is how I solved this problem: (SharepointCopy is my service reference to copy.asmx)
public void UploadFile(String fileName, byte[] file)
{
string[] destinationUrls = {"http://[server]/sites/[listName]/"+fileName};
// load the file into a file stream
byte[] fileBytes = file;
// fill out the metadata
// remark: don't set the Name field, because this is the name of the document
SharepointCopy.FieldInformation titleInformation = new SharepointCopy.FieldInformation
{DisplayName ="Title",
InternalName ="Title",
Type = SharepointCopy.FieldType.Text,
Value ="Test1Title"};
// to specify the content type
SharepointCopy.FieldInformation ctInformation = new SharepointCopy.FieldInformation
{DisplayName ="Content Type",
InternalName ="ContentType",
Type = SharepointCopy.
FieldType.Choice,
Value ="Your content type"};
SharepointCopy.FieldInformation[] metadata = { titleInformation };
// initialize the web service
SharepointCopy.CopySoapClient copyws = new SharepointCopy.CopySoapClient();
// execute the CopyIntoItems method
copyws.CopyIntoItemsCompleted += copyws_CopyIntoItemsCompleted;
copyws.CopyIntoItemsAsync("http://null", destinationUrls, metadata, fileBytes);
}
Many Thanks to Karine Bosch for the solution here: http://social.msdn.microsoft.com/Forums/en/sharepointdevelopment/thread/f135aaa2-3345-483f-ade4-e4fd597d50d4