Here's some info from the UberMenu documentation about this:
Some users have reported issues with caching plugins such as W3TC (W3 Total Cache). The symptom is that the menu is intermittently displayed as an unstyled list on cached pages.
I've investigated this issue, and the cause is that the caching program has not properly cached the menu markup - instead, it seems to revert to either the theme's markup, or some default markup for the menu, thereby resulting in the unstyled list of menu items.
In other words, UberMenu is not being displayed at all. Codewise, UberMenu's display is a combination of two things: HTML and CSS. The CSS (stylesheets) are still loaded; however, the cached page does not display the UberMenu-generated HTML markup. As a result, there is nothing for the CSS to style (the elements which the CSS targets do not exist). The menu being displayed is not UberMenu at all, and that is the problem.
To my knowledge, there is nothing UberMenu can do to change how W3TC chooses to cache the page. UberMenu follows all of the WordPress standards to create the menu markup (via filters and custom navigation walkers).
Please note: I am not sure if this is an issue with the plugin itself, or with the way the plugin has been configured on a particular site.
For help with caching issues, I recommend contacting the author of the caching plugin, as they will certainly have better insight into how the caching works. If there are any recommendations that will help the caching plugin be more compatible, I am certainly willing to consider them.
For now, if you experience this issue, the recommended solution is to disable caching.