You can get really frustrated after checking whether file_uploads = 1, upload_temp_dir is accessible and upload_max_filesize is big enough and everything seems fine.
In this case it's worth checking if the troublemaker is not... the form itself. If there is no enctype="multipart/form-data" in the form tag, you may want to try it. Here is an example of working file upload:
<form name="form" action="index.php" method="post" enctype="multipart/form-data">
<input type="file" name="userfile" />
<input type="submit" value="OK" />
I have found a Nice thread about the above issue which you might be interested in as well.