This might be a file/directory ownership issue. Depending on what kind of host/server you're on, the system "root" user might actually be the owner of all the files in web root.
For a lot of stuff this is fine, but occasionally, EE will choke on something unless it's owned by the web user.
Note, by 'web user' I'm not referring to the 'person uploading the document to your site'. The 'web user' is basically the account that runs web stuff like ExpressionEngine. When your 'website user' is using your website, EE is running under the 'web user' account on the system.
So if the files that EE needs to access are owned by "root", then PHP processes (which runs as the web user) cannot do certain things, even if the files have 777 permissions.
So you need to use the chown command to change the owner on any files in web root, and any files above webroot that EE needs to access.
DO NOT DO THIS, THIS IS AN EXAMPLE
On Ubuntu, the web user is www-data. When I need to change the owner of a directory on my server, I cd to the correct directory and type:
chown -R www-data:www-data ./*
This tells the server to change the owner of everything in this directory to the web user.
Once again, do not type that verbatim, you need to replace www-data with the name of the web user for your server.