Try changing the permissions on the wp-content directory to 766. If you still have problems, try 767, 775 or 777. Once your uploads are working, change the permissions on wp-content back to 755 again and check that everything still works OK.
http://codex.wordpress.org/Changing_File_Permissions
I’ve seen that advice numerous times, and it just plain doesn’t work. Maybe it does for some, but it didn’t for me, and I’ve seen lots of other posts, on these forums and others, from people who never got it working with that sort of trick either. Honestly, this needs to be addressed, because I finally found a solution, and it wasn’t that simple, but wasn’t difficult either once I decided to ignore all the advice that wasn’t working and that maybe it wasn’t something I had done wrong with installation and configuration.
After talking to some folks on another forum and with the folks at pair Networks (my web service provider), I’ve found the problem. Files uploaded by PHP, and folders created by PHP, were being assigned the owner “nobody”. pair support said that I needed to run PHP through php-cgiwrap, which would cause files uploaded by PHP scripts to have my user as the owner. This appears to have solved the problem, and I have switched the permissions on the upload folder back to 755.
For others using pair Networks, here’s the knowledgebase article for their system:
http://kb.pair.com/f25
For everyone else having the same problem and unable to resolve it, talk to your web hosting service provider.