Make sure, access rights are set for the right user/group. Which user/groups is the right one depends on you server setup.
Magento describes two different setups here:
The most important part is:
1) What user is running the setup
2) What user is running the webserver (that in the end handles the http-requests that trigger the magento software)
Well configured servers usually make sure that you don't need to worry about this. But sometimes you can get pretty ugly setups, where access rights need to be set for several users and groups in order to make magento work.
In most cases it is enough to make sure that the webserver´s user has access rights to the appropriate directories.
A simple way to find the apache (webserver) user is by running
ps aux | grep apache in the shell of your server.
More sophisticated answers to finding the apache user can be found here: https://serverfault.com/questions/125865/finding-out-what-user-apache-is-running-as
Make sure what user is running your webserver
Add write privileges to the magento directories to that user