It is probably the case that you are taking the easy (and reasonable) route of inserting it into your theme via widget form rather than inserting the PHP directly into your header code.
I have a similar problem at the moment – combining this plug in with Samsarin’s php plugin to insert it in my theme’s header space – each item in menu being preceded by this dang star/ bullet (mandigo – woot).
I have noticed that another plugin, ad manager, includes an option of treating inserted adverts as a non-widget – thereby providing for neater insertion.
Might I suggest to the maker of this menu plugin that a future version borrow a page from them and make this plugin truly widgitizable? :c)
In the meantime – any tips for persons like me and the original poster on how to disable the bullets in themes? :c) Would be appreciated.