The file uploader (both flash and non-flash) states that it cannot upload an image and that I should check whether the parent directory is writable. The error persists even if wp-content (including wp-content/uploads) is recursively set to mode 777 or owned by www-data (which is the user my web server runs as) or both.
Other files below wp-content such as plugin and theme source files are writable by wordpress. Editing them in the admin panel works. Hence the upload problem is a bug within the file uploader that is hopefully to be fixed soon.
Many people seem to be having the problem (just hit the search).