WP Super Cache Bug with Ubermenu

I’ve experienced the same issue. I’m not 100% sure yet if this is helping because it’s an intermittent issue, but as noted on the plugin author’s docs, this is a potential new fix for the problem:

<!-- mfunc wp_nav_menu( $args ); -->
<?php wp_nav_menu( $args ); ?>
<!-- /mfunc --> 

UPDATE

As of version 2.3 of uberMenu, there is a fix the plugin developer created that I’ve found to work better.

<?php if( function_exists( 'uberMenu_direct' ) ) uberMenu_direct( 'primary' ); ?>

Note: primary is the theme location handle/ID/slug of your WP menu / uberMenu.

Source: http://sevenspark.com/docs/ubermenu-caching