The following is run from the directory where Magento is installed:
find . -type f -exec chmod 644 {} \;
find . -type d -exec chmod 755 {} \;
chmod o+w var var/.htaccess app/etc
chmod 550 mage
chmod -R o+w media
If that is not working, try setting all directories to 775 by doing this:
find . -type f -exec chmod 644 {} \;
find . -type d -exec chmod 775 {} \;
chmod o+w var/.htaccess
chmod 550 mage
If this is a non-production site, and you are still stuck you can do 777 but NEVER on a production server
find . -type f -exec chmod 644 {} \;
find . -type d -exec chmod 777 {} \;
chmod o+w var/.htaccess
chmod 550 mage