Hello,
it seems that the menu module you are using is either not written according to Joomla API standards, so it does not translate the URLs as it shoud, or it is cached. (but I assume that if it would be cached, it should be refreshed by now).
So most likely, I think the module does not parse the links it generates via the JRoute::_ method, which is in fact responsible for calling the SEO engine to create the SEF URLs.
This is of course not problem of JoomSEF then. You have 2 options. You can contact author of the module to adjust it so it is according to standards and works fine or we can do it for you as paid support. (or, if you are familiar with PHP and Joomla coding, you should be able to make the adjustment yourself)