I just installed "W3 total cache" and the settings page says both these things:
Page caching is not available: /usr/share/wordpress/wp-content/advanced-cache.php is not installed. Either the /usr/share/wordpress/wp-content directory is not write-able or another caching plugin installed. This error message will automatically disappear once the change is successfully made.
/usr/share/wordpress/wp-content is write-able. When finished installing the plugin, change the permissions back to the default: chmod 755 /usr/share/wordpress/wp-content.
I checked: the wp-content directory is writable but there is no advanced-cache.php file in there. Why would there be? Does it get automatically installed? Well in this case, it wasn't. I don't know why.
As you can see, installation doesn't work for me with WordPress 3.0.5 multisite.