I've installed wordpress on 2 different websites, both hosted on the same server, with the same settings, etc.
On the 1st one, everything went smoothly.
On the 2nd one, whenever I tried to upload an image to a post it would say it was unable to access the wp-conent/uploads/2009/10 folder and did I have server permission, yadda yadda yadda.
I noticed there was no uploads folder created when I set up wordpress, so I manually created one. Nope, problem still happened. So I temporarily set CHMOD permissions on the newly created uploads folder AND the containing wp-content folder to 777.
The photo upload worked.
I then reset them to 775, and every subsequent upload worked.
Going on that logic, after trying all the other backflips and workarounds suggested for this problem to no avail, I manually created an 'upgrades' folder in wp-content, set CHMOD permissions for 'upgrades', its containing 'wp-content' folder, and its containing root folder to 777 and attempted a plugin upgrade.
I then reset them to CHMOD 755 and attempted to upgrade a 2nd plugin. It also worked.
The trick seems to be to temporarily open up your security for the *first use*, then close it back up again for subsequent use. This way a precident is set for the path and WordPress can find it.
I hope that helps you as it helped me.