The following folders have to be chmod-ed to 777 (readable/writable/executable by all users) for wp-cache to work:
wp-content
wp-content/cache
You can do this from your host’s cpanel or webftp.
If it doesn’t work you can try chmod-ing these too:
wp-content/plugins
wp-content/plugins/wp-cache