Write your own template
Below is the list of templates used by menu.
template/contenttype/menu.phtml
template/contenttype/menu/item-block.phtml
template/contenttype/menu/item-category.phtml
template/contenttype/menu/item-content.phtml
template/contenttype/menu/item-custom.phtml
template/contenttype/menu/item-node.phtml
template/contenttype/menu/item-page.phtml
template/contenttype/menu/item-product.phtml
menu.phtml corresponds to the main template used for displaying menu.
menu/item-* are templates for displaying your item, depending of your item type.
If you want to create a dedicated template for your menu, call it:
template/contenttype/menu-identifier.phtml
Where identifier match your menu unique identifier.
The same method can be applied to menu item template, example:
template/contenttype/menu/item-category-identifier.phtml