It has finally dawned on me what I was doing wrong.

The filename being passed through in the SetValue was not the original filename it was the modified one.

For those interested, here is the final code:-

        public void SaveMedia(newsCollateral NC, long newsId)
    {
        IMediaService ms = ApplicationContext.Current.Services.MediaService;

        string fileName = NC.description.ToLower().Replace(',', '-').Replace(" ", "");
        bool folderExists = false;
        int folderId = 4368; //Folder Id in Media Library

        var request = WebRequest.Create(NC.url);
        request.Timeout = 30000;

        using (var response = (HttpWebResponse)request.GetResponse())
        using (Stream stream = response.GetResponseStream())
        {
            if (response.StatusCode == System.Net.HttpStatusCode.OK)
            {
                Stream streamCopy = new MemoryStream();

                stream.CopyTo(streamCopy);

                IEnumerable<IMedia> getAllChildItems = ms.GetChildren(folderId);

                #region "Loop through all folders in to check if folder exists"
                foreach (IMedia item in getAllChildItems.Where(c => c.ContentType.Name.Equals("Folder")).OrderByDescending(x => x.Name))
                {
                    if (item.Name == newsId.ToString())
                    {
                        folderId = item.Id;
                        folderExists = true;
                        break;
                    }
                }
                #endregion

                #region "Create Folder If It Doesn't Exist"
                if (!folderExists)
                {
                    try
                    {
                        var mediaFolder = ms.CreateMedia(newsId.ToString(), folderId, "Folder");
                        ms.Save(mediaFolder);
                    }
                    catch
                    {
                        throw new Exception("There was a problem creating a new folder - " + folderId);
                    }

                }
                #endregion

                #region "Either Add the File or Update the Existing one"
                int assetID = 0;
                assetID = ms.GetChildren(folderId).Where(c => c.Name == fileName).Select(c => c.Id).FirstOrDefault();

                string origFilename = "";

                Uri uri = new Uri(NC.url);

                origFilename = System.IO.Path.GetFileName(uri.LocalPath);


                if (assetID > 0)
                {
                    try
                    {
                        IMedia existingFile = ms.GetById(assetID);
                        existingFile.SetValue("umbracoFile", origFilename, streamCopy);
                        ms.Save(existingFile);
                    }
                    catch
                    {
                        throw new Exception("There was a problem updating Image - " + assetID);
                    }

                }
                else
                {
                    try
                    {
                        IMedia mediaFile = ms.CreateMedia(fileName, folderId, "Image");
                        mediaFile.SetValue("umbracoFile", origFilename, streamCopy);
                        ms.Save(mediaFile);

                    }
                    catch (Exception ex)
                    {

                        throw new Exception("There was a problem saving the image - " + fileName);
                    }

                }
                #endregion

            }

        }

    }