I have the same problem as sauerland. http://ww.wp.xz.cn/support/topic.php?id=53381&replies=5 I’m waiting for reply from my host administrator now.
Also interesting is that plugin Image Browser ( http://fredfred.net/skriker/index.php/iimage-browser ) without any problems uploads and deletes files to/from that directories. 🙂
My WP has problem only with making year directory. It’s necessary only to create “2005” manually and set chmod for it. Then WP creates “12” inside and shows message which is quoted above.
I’ll ask my administrator again.