Error Message when uploading Showcase Theme

Hi, I've uploaded the new wordpress version 3.4.1 and now want to change the theme to Showcase. When I try and do this I'm coming up with the following error message "Unable to create directory /var/www/html/qmp.net.au/wordpress/wp-content/uploads/2012/07. Is its parent directory writable by the server? I've contacted my host server who explains there is nothing wrong on his side - can anyone tell me why this is happening please?