I'm thinking perhaps you're running into a time-out issue waiting for the upload to finish, and not really a size limitation.
Here's some info from the PHP folks that may be candidates for checking:
This sets the maximum time in seconds a script is allowed to run before it is terminated by the parser. This helps prevent poorly written scripts from tying up the server. The default setting is 30. When running PHP from the command line the default setting is 0.
The maximum execution time is not affected by system calls, stream operations etc. Please see the "set_time_limit()" function for more details.
Your web server can have other timeout configurations that may also interrupt PHP execution. Apache has a Timeout directive and IIS has a CGI timeout function. Both default to 300 seconds. See your web server documentation for specific details.
This sets the maximum time in seconds a script is allowed to parse input data, like POST, GET and file uploads.
Note: The set_time_limit() function and the configuration directive max_execution_time only affect the execution time of the script itself. Any time spent on activity that happens outside the execution of the script such as system calls using system(), stream operations, database queries, etc. is not included when determining the maximum time that the script has been running. This is not true on Windows where the measured time is real.
Additionally here's some info on checking/setting CGI Timeout in IIS5 and 6.