Thanks for the hint, esmi. The apache error log contained this line:
/usr/sbin/apache2: symbol lookup error: /usr/lib/php5/20100525+lfs/suhosin.so: undefined symbol: php_mb_encoding_translation
which I think was caused by a mistake I made when updating to php 5.4.
I uninstalled suhosin and uploading works now (although I did have to change wp-contents/uploads permissions to 777).
Thank you!
