Cannot upload image 2.1 version

I cannot upload a simple image using wordpress. Yes, I have changed two directories to 777 and no luck.
This is the infamous error we are seeing a lot:

Unable to create directory /var/www/vhosts/” “/httpdocs/wp-content/uploads/2007/05. Is its parent directory writable by the server?

Answer to this is yes it is writable, but still not working. Anyone have suggestions to fix this. Seems to be a recurring big problem with no solutions I have seen. Hope you can help my craziness with this