Yes, the folder has the correct permissions.
Seems like it is a known issue -
wordpress 2.6 image upload problem - Google Search - with custom paths for image folders.
I really really really hate the new upload photo feature in Wordpress. Has anybody installed any plugins to remove it and replace it with the old functionality?