First I will just tell you how my wordpress hierarchy looks like:

/var/www has all of the wordpress files, which is different from how it is normally set up as /var/www/wordpress (symlinked to /usr/share/wordpress). So var/www contains all of the files that /usr/share/wordpress would have, and /usr/share/wordpress is symlinked to /var/www, with an extra /var/www/wordpress symlinked to /var/www to prevent possible compatibility issues.

When uploading a file like a favicon or a .zip-ped theme, everything works fine, and when checking if the theme/favicon is uploaded, wordpress shows that it is, and points to a directory that it thinks that it had created, like http:/localhost/wp-content/uploads/2012/..., which it had not, because the uploads folder is empty!

And so there is a broken link on the internet and the theme is displayed but it has just plain text (because it had reverted to a plain theme I think)

Please help! I am sorry for such a long post but this is really quite a troublesome problem.

I have chowned /var/www and /usr/share/wordpress to www-data.