Error uploading images – Not a dir permissions issue

I get the following error when I try to upload something:

The uploaded file could not be moved to /var/www/vhosts/xxxxxxx.com/httpdocs/wp-content/uploads/2007/10.

/var/www/vhosts/xxxxxx.com/httpdocs/wp-content/uploads/ and everything under it is set to 777 and still nothing happens. How can I fix this?

BTW, it can create directories, just not write into them.