try to increase post_max_size and upload_max_filesize values in php.ini.
I think i had those issues in the past and can remember darkly that this was the solution. Nearby make sure your request will not time out (server and client side) or try to upload those huge files via ftp or webdav - or anything else you prefer.
See this site for a simple and stupid explanition and background-info: http://drupal.org/node/97193
