UPDATE

OK thanks for the comments I've updated my code to show you what I have now including the changes to the location of the component. Please see below:

    public static string Create(CoreServiceClient client, string componentId, string targetComponentLocationId)
{
    var compData = (ComponentData)client.Read(componentId, new ReadOptions());

    // Start creating component
    var component = (ComponentData)client.GetDefaultData(ItemType.Component, compData.LocationInfo.OrganizationalItem.IdRef);
    component.Id = "tcm:0-0-0";
    component.Title = compData.Title;
    component.Schema.IdRef = compData.Schema.IdRef;
    component.Content = compData.Content;

    if (!String.IsNullOrEmpty(compData.Metadata))
    {
        component.Metadata = compData.Metadata;
    }

    // Check and create binary component
    if (compData.BinaryContent != null)
    {
        string origFilename = compData.BinaryContent.Filename;
        string extension = origFilename.Substring(origFilename.LastIndexOf('.') + 1);
        string tempPath = string.Empty;

        using (var suClient = new StreamUploadClient("streamUpload_basicHttp"))
        {
            using (var sdClient = new StreamDownloadClient("streamDownload_basicHttp"))
            {
                string file = "C:\\MyTempLocation\\" + Path.GetFileName(compData.BinaryContent.Filename);

                using (var fs = File.Create(file))
                {
                    byte[] binaryContent = null;

                    var tempStream = sdClient.DownloadBinaryContent(compData.Id);
                    var memoryStream = new MemoryStream();
                    tempStream.CopyTo(memoryStream);
                    binaryContent = memoryStream.ToArray();

                    tempPath = suClient.UploadBinaryContent(origFilename, memoryStream);
                }
            }
        }

        // Find multimedia type
        var list = client.GetSystemWideList(new MultimediaTypesFilterData());
        var multimediaType = list.OfType<MultimediaTypeData>().Single(mt => mt.FileExtensions.Contains(extension));

        // Set binary content of component
        component.BinaryContent = new BinaryContentData
        {
            UploadFromFile = tempPath,
            Filename = origFilename,
            MultimediaType = new LinkToMultimediaTypeData { IdRef = multimediaType.Id }
        };
    }

    component.LocationInfo = new LocationInfo
    {
        OrganizationalItem = new LinkToOrganizationalItemData
        {
            IdRef = targetComponentLocationId
        }
    };

    try
    {
        component = (ComponentData)client.Create(component, new ReadOptions());
    }
    catch (Exception ex)
    {
        _log.ErrorFormat("Unable to create component: {0}", ex);
    }

    return component.Id;
}

When I run this it does work but when I go into Tridion and open up the binary component I see the following message in the preview

HTTP 404: File not found, reverting to mimetype

I'm pretty sure I've seen Tridion do this before but even when I go to C:\\MyTempLocation\\ I try opening the binary and its empty.

Can anyone see a problem with my approach here?