Make sure the PHP parameter you are checking is exactly upload_max_filesize. Also, in Joomla admin go to System Information and see what it shows there in your PHP information. Search for upload_max_filesize there. Sometimes people change this in PHP, but without an Apache restart it doesn't apply.
Also check your max_execution_time and trying increasing that if it is less than 60. Set it for 60 or 90.
Beyond this, it would be a problem tied to permissions. You can try the "Install From Directory" option also.