This is a very frustrating problem!
I think it is a combination of permission and ownership thing.
What worked for me: (not really a fix!)
I manually created the follows directories: uploads/2008/08
CHMOD them 777
CHMOD wp-content to 777
I manually made the directories, coz I got the error msg otherwise.
Then on shell,
CHOWN user:root /path/wp-content/
CHOWN user:root /path/wp-content/uploads/
This works on one of my blogs. The new images are created with user & group apache:apache. But it doesn’t work on my other blog. On the other blog, the images get uploaded, but are broken. I can’t access the images directly either! I don’t know if that is a htaccess or ownership problem? Anyone help !