I am getting this same error. All the folders have write access but I cant see how it is failing. Perhaps its a problem with the write permissions of the tmp folder? Im using a linux based server through Media Temple if that helps.
OK. I fixed my problem. I set write permissions to the upload folder, but I needed to set it on the wp-content folder as well for some reason.
Also, this was originally an issue with the wp-ecommerce plugin (coldnt upload photos for products) but setting permissions for the plugins folder to 777 fixed that too.
Not the most secure but its the only thing that worked.
Some servers require you to change file permissions to 777 from 755 for your upload folder depending on how you set it up in your settings e.g.
= wp-content/uploads/2008/10 — the /10 folder CHMOD to 777
= wp-content/uploads — the /uploads folder CHMOD to 777