What kind of bandwidth do you have and do you see different file sizes if someone with a faster or slower connection than you tries an upload?
If so, and you're seeing errors like 'CGI.pm: Server closed socket during multipart read (client aborted?).' in your error logs (you are checking your error logs, right?), then you might be running into Apache's TimeOut or something similar.
A workaround for such (or possibly something else to try) is to fork() your own server for the duration of an upload.
--k.