After a few hours of debugging I figured out the problem.
Here is a diff.
> diff TotalCache.php TotalCache.spf.php
< add_menu_page('Performance', 'Performance', 'manage_options', 'w3tc_general', '', plugins_url('w3-total-cache/inc/images/logo_small.png'));
> add_menu_page('Performance', 'Settings', 'manage_options', 'w3tc_general', '', plugins_url('w3-total-cache/inc/images/logo_small.png'));
The problem is that the plugin is registering pages as
 => toplevel_page_w3tc_general
 => performance_page_w3tc_pgcache
 => performance_page_w3tc_minify
 => performance_page_w3tc_dbcache
 => performance_page_w3tc_objectcache
 => performance_page_w3tc_browsercache
 => performance_page_w3tc_mobile
 => performance_page_w3tc_cdn
 => performance_page_w3tc_faq
 => performance_page_w3tc_support
 => performance_page_w3tc_install
 => performance_page_w3tc_about
But the plugin has them located at "settings_page..."
since the page it's looking for doesn't exist in the method 'user_can_access_page', this block fails every time.
if ( !isset($_registered_pages[$hookname]) )
Not sure why it's happening and especially why it's not happening to everyone. I'll bet there's a better way of fixing it, but I'm just happy to have something that works.