I am running Fedora 13 (126.96.36.199) and have self-hosted WordPress for several years. Before upgrading from 2.5 to 3.0, I decided to clean up, pare down and basically start from scratch with a clean install.
After 3 fresh installations of 3.0 I basically gave up with media uploads. I was constantly getting errors using either the native or flash uploader saying I didn't have permission to move the file to the "uploads" folder.
I had tried chmod'ing 777 /wp-content/uploads, with and without the leading and trailing slashes, I went so far as to chmod 777 to the root /var/www/html/blog.... . I had checked and unchecked the "Organize my uploads into month- and year-based folders". I had chown'd everything to apache, root and my regular user name, all with the same failing results. Then I started doing what I thought was 3 different fixes in different combinations, hoping to hit the jackpot.
My problem turned out that when I modified SELinux to disabled in /etc/selinux/config, "disabled" didn't mean disabled apparently even after several reboots. I was getting errors "SELinux prevented httpd (/usr/sbin/httpd) write access to uploads." in the system messages.
I needed to chcon the httpd_sys_rw_content_t for 'uploads' and WordPress was finally able to upload media again.
This might be a one-off solution (I doubt hosting companies will let you mess with SELinux settings), but for those of you searching for a solution like I was and the standard chmod 777....uncheck month/year box....chown root or apache....etc, isn't working for you, check out SELinux's settings. It worked for me.