Using the wordpress admin/settings/misc page I checked "organize my uploads into month- and year-based folders".
When trying to upload an image I get the following error message:
Unable to create directory [...]/uploads/2008/06". Is its parent directory writeable by server?
Changing the permissions of the upload folder to 777 (just for testing!) leads to the same error message, but this time the directory 2008 has been created by "www-data" (or maybe "nobody", depends on the server).
Nevertheless, the 06 subdirectory is still missing.
This is a permission/ownership problem which can be solved - if you have root access - and if you manage to contemplate this mantra:
When safe_mode is on, PHP checks to see if the owner of the current script matches the owner of the file to be operated on by a file function or its directory. - http://de.php.net/features.safe-mode
Meaning: if www-data executes your scripts (owned by you, not www-data) wordpress will create a year-directory which is owned by www-data. Afterwards it will create the month-subdirectory, but now the owner of the script (you) does not match the owner of the directory (www-data) it operates on.
Changing the owner of all WordPress files to www-data should do the trick, but isn´t really an option. Just changing only the group-ids, while turning safe_mode_gid in the php.ini file on should work.
But actually turning php safe_mode off seems to be the way to go.
Hope this helps some people who encountered the same problem,