Unless you are running suexec, your $upload_dir has to be mode 777 (world writable) because the server runs at the lowest permission possible. You seem to be making your uploaded file 0777, but the directory it goes into must be 0777. It can get tricky. :-)
No, it doesn't have to be world writable; it just has to be writable by the uid which the CGI (and/or web server) is running as. Often in shared hosting setups you can't achieve this other than by making the directory wide open, but if you've got more control it's better to avoid opening things up more than you have to.</pedant>
The cake is a lie.
The cake is a lie.
The cake is a lie.
Thats why I prefaced it with "with suexec". That is what I'm familiar with under apache, that lets the apache run as the user in his own home dir. But it's been a few years since I've done an httpd.conf file setup.... it's amazing all the options and juggling they do now. It's probably possible nowadays to make an .htaccess edit, to get write permissions. :-)