¿Tambien post_max_size? Y quizas tambien el campo oculto del formulario MAX_FILE_SIZE.
Revisa
http://www.php.net/manual/en/features.file-upload.php . Pone que se crea una variable mas a partir de 4.2 que indica el error que se ha producido.
Tambien comenta algo del max_execution_time . Pruebalo.
Suerte.