How to enable special characters in Drupal Menu?
I guess that you can review in the nice_menus.module file, specifically in theme_nice_menu_tree() module function to parse/filter/encode/replace each hexadecimal string that seems be pushed by menu_item_link($mid) or $mid string. Remember do this kind of test with a copy of your production site. I have not tried this suggestions, sorry, I only guess after a rough review of the code. I think that could be useful. - @cigotete