Silly wordpress issue – trying to upload an image, everything seems to go smoothly accept that the uploaded image isn’t there, the links to the images are broken. Permissions for the upload dir look fine too. Chances are, somewhere apache is logging a line like

PHP Warning: POST Content-Length of 15148998 bytes exceeds the limit of 8388608 bytes in Unknown on line 0, referer: https://your_site.com/your_uri/wp-admin/themes.php?page=custom-background

So what is needed is a higher upload limit. In /etc/php5/apache2/php.ini (or corresponding file in your distro, if you use Apache), change post_max_size and upload_max_filesize to something appropriate.

An additional issue I had is where my blog is not on the root of its vhost/domain. So check in what filesystem directory the uploaded files end up, and whether the uploads link points at the right place on your filesystem. The wordpress config files should have the upload directory specified in e.g., on Ubuntu/Debian, /etc/wordpress/config-your_site.com.php.