nice_menus.css is not loading after page refresh

Just upgraded from 2.1 to 2.5 and I get this weird issue with on of my nice menu block. After I clear cache, everything works great, until i refresh the page or navigate to another page, which cause nice_menus NOT to load the default nice_menus.css.

Might be a issue with Blockcache alter that we use to cache the menu block. Everything works great when the block isn't cache.

Maybe this should be a Blockcache alter issue? Any feedback or anyone experiencing this?