I am having a similar but different problem. Everything on the blog (WP version 2.7.1) is working perfectly, but when I try to upload an image (either through the Flash or the Browser dialogue box), I get the following error message:
Unable to create directory /home/business/public_html/blog/wp-content/uploads/2009/05. Is its parent directory writable by the server?
I have checked the permissions on the parent directories and they are set to 755. When I change them to 666 (which I had to do for some other files), it breaks the blog. I read through the suggested article above and none of it seems to apply. Any ideas out there?