We added the key but the problems remain. The "Fasle" value looked like a typo so we added:
<appSettings>
<add key="CuteWebUI.AjaxUploader.RewritePath" value="False" />
</appSettings>
For testing purposes we set up a IIS Website using the demo websites. We are currently using the "Framework 2.0-Csharp-NoAjax\selecting-multiple-files.aspx" for testing and are able to reproduce said errors with client certificates enabled.
We use 3 x 20MB files for testing and are uploading with speeds between 500-1000 kbits/s.