Logged a ticket at Support and the following action resolved the issue:
ASP.NET rewriter module is the cause of the problem. It seems that ASP has a separate setting for the maximum request length that can be passed through it. See http://msdn.microsoft.com/en-us/library/e1f13641%28v=vs.80%29.aspx for more details, and to see that the setting 'maxRequestLength' has a default of 4096KB.
Could you please test this by adding the following XML to the 'system.web' node (next to the 'customErrors' node and again, adjust as needed): <httpruntime executiontimeout="”100000″" maxrequestlength="”2000000″"/>
Also we added the following to the web.config file: <security> <requestfiltering> <requestlimits maxallowedcontentlength="”2000000000″"/> </requestfiltering> </security>
Which sets the max upload to 2GB. This setting was not sufficient and the rewriter adjustment was required as well.